// By rbtree (https://rbtree.archi) :\
// Please submit with C++14!
#define A85 g3[g1[i][j].first].emplace_back(
#define A84 printf("%lld
", dist3[n]);
#define A83 pq.emplace(dist[i.first],
#define A82 dist2[g2[i][j].first]));
#define A81 priority_queue<pair<tp,
#define A80 dist1[g1[i][j].first])
#define A7F array<vector<pair<tp,
#define A7E g2[v].emplace_back(u,
#define A7D g1[v].emplace_back(u,
#define A7C greater<pair<tp,
#define A7B pq.top().second;
#define A7A (!vis[i.first])
#define A79 dist.fill(-1ull
#define A78 g2[i][j].second
#define A77 g1[i][j].second
#define A76 vector<pair<tp,
#define A75 (dist[i.first]
#define A74 (pq.emplace(0,
#define A73 dist[i.first]
#define A72 g1[i].size();
#define A71 vis.fill(0);
#define A70 array<bool,
#define A6F (!vis[loc])
#define A6E dijkstra(1,
#define A6D dijkstra(n,
#define A6C dijkstra(tp
#define A6B pq.size();)
#define A6A __Negitive
#define A69 getchar())
#define A68 getchar();
#define A67 i.first);
#define A66 __Read();
#define A65 (dist1[i]
#define A64 (dist2[i]
#define A63 array<tp,
#define A62 dist[loc]
#define A61 constexpr
#define A60 pq.pop();
#define A5F i.second)
#define A5E namespace
#define A5D i.second;
#define A5C __Read()
#define A5B __Value;
#define A5A ~__Value
#define A59 vis[loc]
#define A58 Hat_N>&
#define A57 __Value
#define A56 (__Char
#define A55 (auto&&
#define A54 (size_t
#define A53 e[loc])
#define A52 dist[s]
#define A51 50003;
#define A50 Hat_N>
#define A4F main()
#define A4E dist2,
#define A4D dist3,
#define A4C dist3;
#define A4B __Char
#define A4A signed
#define A49 return
#define A48 dist1,
#define A47 (m--)
#define A46 using
#define A45 while
#define A44 long;
#define A43 Hat_N
#define A42 tp>>>
#define A41 dist,
#define A40 tp>>,
#define A3F std;
#define A3E ++j)
#define A3D g1);
#define A3C char
#define A3B ++i)
#define A3A tp>,
#define A39 g3);
#define A38 g2);
#define A37 vis;
#define A36 ra);
#define A35 15);
#define A34 long
#define A33 void
#define A32 bool
#define A31 45;
#define A30 57;
#define A2F for
#define A2E g1,
#define A2D g3;
#define A2C g2,
#define A2B loc
#define A2A pq;
#define A29 ra,
#define A28 s);
#define A27 ra;
#define A26 58;
#define A25 (tp
#define A24 15;
#define A23 2);
#define A22 0;
#define A21 n;
#define A20 (;
#define A1F >>
#define A1E &&
#define A1D ==
#define A1C i,
#define A1B e)
#define A1A <=
#define A19 !=
#define A18 47
#define A17 if
#define A16 1;
#define A15 10
#define A14 48
#define A13 s,
#define A12 ||
#define A11 tp
#define A10 ?
#define AF >
#define AE =
#define AD i
#define AC <
#define AB j
#define AA 1
#define A9 :
#define A8 *
#define A7 &
#define A6 u
#define A5 m
#define A4 +
#define A3 {
#define A2 v
#define A1 }
#define A0 n
#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 A86 A46 A11 AE A34 A44 A11 A66 A46 A5E A3F
#define A87 A61 A11 A43 AE A51 A33 A6C A13 A63 A58
#define A88 A41 A7F A40 A58 A1B A3 A81 A3A A76 A40
#define A89 A7C A42 A2A A70 A50 A37 A79 A1F A23 A71
#define A8A A52 AE A22 A2F A74 A28 A6B A3 A11 A2B
#define A8B AE A7B A60 A17 A6F A3 A59 AE A16 A2F
#define A8C A55 AD A9 A53 A3 A17 A75 AF A62 A4
#define A8D A5F A3 A73 AE A62 A4 A5D A17 A7A A3
#define A8E A83 A67 A1 A1 A1 A1 A1 A1 A4A A4F
#define A8F A3 A11 A0 AE A29 A5 AE A27 A63 A50
#define A90 A48 A4E A4C A7F A40 A50 A2E A2C A2D A45
#define A91 A47 A3 A11 A6 AE A29 A2 AE A27 A7D
#define A92 A36 A7E A36 A1 A6D A48 A3D A6D A4E A38
#define A93 A2F A25 AD AE A16 AD A1A A21 A3B A3
#define A94 A2F A54 AB AE A22 AB AC A72 A3E A3
#define A95 A85 A1C A65 A4 A77 A19 A80 A4 A64 A4
#define A96 A78 A19 A82 A1 A1 A6E A4D A39 A84 A49
#define A97 A22 A1 A11 A5C A3 A32 A6A AE A22 A3C
#define A98 A4B AE A68 A11 A5B A2F A20 A4B AC A14
#define A99 A12 A4B AF A30 A4B AE A69 A3 A6A AE
#define A9A A4B A1D A31 A1 A57 AE A4B A7 A24 A2F
#define A9B A56 AE A68 A4B AF A18 A1E A4B AC A26
#define A9C A4B AE A69 A3 A57 AE A57 A8 A15 A4
#define A9D A56 A7 A35 A1 A49 A6A A10 A5A A4 AA
#define A9E A9 A5B A1 
#define A9F A86 A87 A88 A89 A8A A8B A8C A8D A8E A8F
#define AA0 A90 A91 A92 A93 A94 A95 A96 A97 A98 A99
#define AA1 A9A A9B A9C A9D A9E 
#define AA2 A9F AA0 AA1 
#define AA3(__FOX__) __FOX__
AA3(AA2)