#include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i--;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue using namespace std; typedef vector vi; typedef vector vvi; typedef long long ll; typedef vector< ll> vl; typedef vector vvl; typedef unsigned long long ull; typedef vector vu; typedef vector vvu; typedef double dbl; typedef vector vd; typedef vector vvd; typedef string str; typedef vector vs; typedef vector vvs; typedef pairpii; typedef vectorvpii; typedef mapmii; typedef pair< ll, ll>pll; typedef vectorvpll; typedef map< ll, ll>mll; typedef pairpdd; typedef vectorvpdd; typedef mapmdd; typedef pairpss; typedef vectorvpss; typedef mapmss; typedef pair< ll,int>pli; typedef vectorvpli; typedef map< ll,int>mli; typedef pairpdi; typedef vectorvpdi; typedef mapmdi; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){for(auto a:v){s<void print(T x){cout<vector>dijkstra(const vector>>E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstT max(const vectora){T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:~-m+~a%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){return pow(x,p-2,p);} vpll fact(const int n,const int p){vpll v(n+1);v[0].first=1;foor(i,1,n){v[i].first=v[i-1].first*i%p;}v[n].second=inv(v[n].first,p);roof(i,n,1){v[i-1].second=v[i].second*i%p;}return v;} ll C2(const int n){return(ll)n*~-n/2;} ll sum(const vi a){ll s=0;for(int e:a){s+=e;}return s;} ll sum(const vl a){ll s=0;for(ll e:a){s+=e;}return s;} ll segsum(vl&s,int l,int r){l|=s.size()/2;r|=s.size()/2;if(l==r){return s[l];}ll z=s[l]+s[r];for(;l/2=1;i/=2){s[i/2]=s[i]+s[i^1];}} ll fib(const ll n,const int m){ll a,b,c,d,A,B,C,D;a=1;b=0;c=0;d=1;rf(i,63){A=a*a+b*c;B=a*b+b*d;C=c*a+d*c;D=c*b+d*d;if(n>>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} // (int) * (int) => (int) // (int) / (int) => (int) main(){cin.tie(0);ios::sync_with_stdio(false); int N,M; cin>>N>>M; vi a(M),b(M),c(M); fr(i,M)cin>>a[i]>>b[i]>>c[i]; vi v; fr(i,N)v<