ll@N,@M,W[N]{-1d9};VVLL E[N];rep(M){ll@(--u,--v,h);E[u].push_back({-h,v});E[v].push_back({-h,u});}set<VLL>S;S.insert({-1d9,0});while(S.size()){auto a=*(S.begin());S.erase(a);if(a[0]>W[a[1]])continue;for(auto b:E[a[1]])if((b[0]>?=a[0])<W[b[1]])W[b[1]]=b[0],S.insert(b);}if((M=W[N-1])<0)wt(-M);else wt("NaN");