// By rbtree (https://rbtree.archi) :\
// Please submit with C++14!
#define A9F printf("%lld %lld
", dist[b].first, dist[b].second);
#define A9E // freopen("cowroute.out", "w", stdout);
#define A9D // freopen("cowroute.in", "r", stdin);
#define A9C e[temp[j]].emplace_back(temp[i],
#define A9B dist.fill(make_pair(-1ull
#define A9A make_pair(dist[j].first
#define A99 make_pair(comp.cost,
#define A98 array<vector<Item>,
#define A97 airline(_airline)
#define A96 make_pair(cost,
#define A95 min(dist[i.to],
#define A94 operator<(const
#define A93 array<pair<tp,
#define A92 comp.airline);
#define A91 dist[j].second
#define A90 (dist[b].first
#define A8F puts("-1 -1");
#define A8E Item(temp[i],
#define A8D airline(-1ull
#define A8C make_pair(0,
#define A8B vis.fill(0);
#define A8A cost(_cost),
#define A89 i.airline));
#define A88 __Initer_t()
#define A87 dijkstra(a);
#define A86 array<bool,
#define A85 dijkstra(tp
#define A84 e[temp[j]])
#define A83 cost(-1ull
#define A82 getchar();
#define A81 __Initer_t
#define A80 __Negitive
#define A7F dist[i.to]
#define A7E getchar())
#define A7D array<tp,
#define A7C __Initer;
#define A7B namespace
#define A7A __Read();
#define A79 _airline)
#define A78 dist[j]))
#define A77 constexpr
#define A76 ~__Value
#define A75 __Read()
#define A74 airline;
#define A73 (!vis[k]
#define A72 __Value;
#define A71 to(_to),
#define A70 to(-1ull
#define A6F temp[i])
#define A6E airline)
#define A6D i.cost,
#define A6C Item(tp
#define A6B dist[s]
#define A6A dist[k]
#define A69 __Value
#define A68 (auto&&
#define A67 temp[i]
#define A66 (__Char
#define A65 Item()
#define A64 main()
#define A63 min(l,
#define A62 break;
#define A61 struct
#define A60 return
#define A5F signed
#define A5E _cost,
#define A5D Hat_N>
#define A5C (-1ull
#define A5B vis[j]
#define A5A __Char
#define A59 temp;
#define A58 using
#define A57 while
#define A56 (l.to
#define A55 (m--)
#define A54 -1ull
#define A53 1003;
#define A52 Hat_N
#define A51 Item&
#define A50 comp)
#define A4F const
#define A4E cost,
#define A4D dist;
#define A4C e[j])
#define A4B long;
#define A4A std;
#define A49 ++j)
#define A48 (!f)
#define A47 Item
#define A46 cost
#define A45 long
#define A44 ++k)
#define A43 _to,
#define A42 15);
#define A41 vis;
#define A40 void
#define A3F bool
#define A3E tp>,
#define A3D ++i)
#define A3C else
#define A3B j));
#define A3A 2));
#define A39 char
#define A38 0);
#define A37 2))
#define A36 (!j
#define A35 45;
#define A34 j);
#define A33 2),
#define A32 58;
#define A31 15;
#define A30 ra,
#define A2F ra;
#define A2E for
#define A2D (tp
#define A2C to,
#define A2B 57;
#define A2A &&
#define A29 <=
#define A28 >>
#define A27 2,
#define A26 ==
#define A25 e;
#define A24 tp
#define A23 if
#define A22 (;
#define A21 n;
#define A20 10
#define A1F 48
#define A1E i;
#define A1D 47
#define A1C 0;
#define A1B {}
#define A1A 1;
#define A19 2)
#define A18 ||
#define A17 s)
#define A16 };
#define A15 k;
#define A14 ?
#define A13 >
#define A12 &
#define A11 <
#define A10 f
#define AF :
#define AE =
#define AD i
#define AC 1
#define AB -
#define AA b
#define A9 l
#define A8 n
#define A7 j
#define A6 +
#define A5 {
#define A4 a
#define A3 *
#define A2 }
#define A1 k
#define A0 m
#include <time.h>
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#define ra __Read()
#define AA0 A58 A24 AE A45 A4B A24 A7A A58 A7B A4A
#define AA1 A77 A24 A52 AE A53 A61 A47 A5 A24 A2C
#define AA2 A4E A74 A65 AF A70 A28 A33 A83 A28 A33
#define AA3 A8D A28 A19 A1B A6C A43 A24 A5E A24 A79
#define AA4 AF A71 A8A A97 A1B A3F A94 A51 A50 A4F
#define AA5 A5 A60 A96 A6E A11 A99 A92 A2 A16 A24
#define AA6 A8 AE A52 AB A1A A93 A3E A5D A4D A98
#define AA7 A5D A25 A40 A85 A17 A5 A86 A5D A41 A9B
#define AA8 A28 A27 A54 A28 A3A A8B A6B AE A8C A38
#define AA9 A2E A2D AD AE A1A AD A11 A21 A3D A5
#define AAA A24 A7 AE A1C A2E A2D A1 AE A1A A1
#define AAB A29 A21 A44 A5 A23 A73 A2A A36 A18 A6A
#define AAC A11 A78 A5 A7 AE A15 A2 A2 A5B AE
#define AAD A1A A2E A68 AD AF A4C A5 A7F AE A95
#define AAE A9A A6 A6D A91 A6 A89 A2 A2 A2 A5F
#define AAF A64 A5 A24 A4 AE A30 AA AE A30 A0
#define AB0 AE A2F A57 A55 A5 A24 A46 AE A30 A1
#define AB1 AE A2F A7D A5D A59 A2E A2D AD AE A1A
#define AB2 AD A29 A15 A3D A5 A67 AE A2F A2E A2D
#define AB3 A7 AE A1A A7 A11 A1E A49 A5 A3F A10
#define AB4 AE A1C A2E A68 A9 AF A84 A5 A23 A56
#define AB5 A26 A6F A5 A9 AE A63 A8E A4E AD AB
#define AB6 A3B A10 AE A1A A62 A2 A2 A23 A48 A5
#define AB7 A9C A4E AD AB A34 A2 A2 A2 A2 A87
#define AB8 A23 A90 A26 A5C A28 A37 A5 A8F A2 A3C
#define AB9 A5 A9F A2 A60 A1C A2 A61 A81 A5 A88
#define ABA A5 A9D A9E A2 A2 A7C A24 A75 A5 A3F
#define ABB A80 AE A1C A39 A5A AE A82 A24 A72 A2E
#define ABC A22 A5A A11 A1F A18 A5A A13 A2B A5A AE
#define ABD A7E A5 A80 AE A5A A26 A35 A2 A69 AE
#define ABE A5A A12 A31 A2E A66 AE A82 A5A A13 A1D
#define ABF A2A A5A A11 A32 A5A AE A7E A5 A69 AE
#define AC0 A69 A3 A20 A6 A66 A12 A42 A2 A60 A80
#define AC1 A14 A76 A6 AC AF A72 A2 
#define AC2 AA0 AA1 AA2 AA3 AA4 AA5 AA6 AA7 AA8 AA9
#define AC3 AAA AAB AAC AAD AAE AAF AB0 AB1 AB2 AB3
#define AC4 AB4 AB5 AB6 AB7 AB8 AB9 ABA ABB ABC ABD
#define AC5 ABE ABF AC0 AC1 
#define AC6 AC2 AC3 AC4 AC5 
#define AC7(__FOX__) __FOX__
AC7(AC6)