#include using namespace std; using ll=long long; using A=array; constexpr ll INF=1e18; struct edge{ int to; ll cost; }; bool chmin(ll&a,ll b){return a>b?a=b,true:false;} vectorG[105]; mapdist[105]; ll T[105]; int main(){ int N,M; cin>>N>>M; for(int i=0;i>A>>B>>C; G[A-1].push_back({B-1,C}); G[B-1].push_back({A-1,C}); } for(int i=0;i>T[i]; priority_queue,greater>PQ; PQ.push({0,0,0}); dist[0][0]=0; while(!PQ.empty()){ auto[c,v,p]=PQ.top();PQ.pop(); if(v==N-1){ cout<