1 #include 2 #include 3 #include 4 #include 5 #includestring>
6 #include
7 #include 8 #include 9
10 using namespace std;
11 typedef long long ll;
12 const int maxm=5e4*2+2;
13 const int maxn=1e3+2;
14 const int inf=0x3f3f3f3f;
15 int n,m;
16 struct node
17 {
18 int to;
19 int nxt;
20 int w;
21 }e[maxm];
22 int head[maxn];
23 int tot;
24 bool vis[maxn];
25 int dis[maxn];
26 int pv[maxn];
27 int pe[maxn];
28 typedef pairint,int> pii;
29 void init()
30 {
31 memset(head,-1,sizeof(head));
32 tot=0;
33 }
34
35 void add(int u,int v,int w)
36 {
37 e[tot].to=v;
38 e[tot].w=w;
39 e[tot].nxt=head[u];
40 head[u]=tot++;
41 }
42
43 int Dij(int x)
44 {
45 priority_queue,greater >pq;
46 memset(vis,false,sizeof(vis));
47 memset(dis,inf,sizeof(dis));
48 dis[1]=0;
49 pq.push(make_pair(dis[1],1));
50 // pq.push(pii(dis[1],1));
51 while(!pq.empty())
52 {
53 pii cur=pq.top();
54 pq.pop();
55 int u=cur.second;
56 if(vis[u]) continue;
57 vis[u]=true;
58 for(int i=head[u];i!=-1;i=e[i].nxt)
59 {
60 if(i==x) continue;
61 int w=e[i].w;
62 int v=e[i].to;
63 if(dis[u]+wdis[v])
64 {
65 dis[v]=dis[u]+w;
66 pq.push(make_pair(dis[v],v));
67 if(x==-1)
68 {
69 pv[v]=u;
70 pe[v]=i;
71 }
72 }
73 }
74 }
75 return dis[n];
76 }
77
78 int Solve()
79 {
80 if(Dij(-1)==inf)
81 {
82 return -1;
83 }
84 int ans=0;
85 for(int i=n;i!=1;i=pv[i])
86 {
87 ans=max(ans,Dij(pe[i]));
88 if(ans==inf)
89 {
90 return -1;
91 }
92 }
93 return ans;
94 }
95 int main()
96 {
97 int T;
98 scanf("%d",&T);
99 while(T--)
100 {
101 init();
102 scanf("%d%d",&n,&m);
103 while(m--)
104 {
105 int u,v,w;
106 scanf("%d%d%d",&u,&v,&w);
107 add(u,v,w);
108 add(v,u,w);
109 }
110 int ans=Solve();
111 printf("%d\n",ans);
112 }
113 return 0;
114 }
