#include<bits/stdc++.h> #define int long long using namespace std; const int INF=1e18; void chmin(int&a,int b){if(a>b)a=b;} int N,M,dist[110][110]; signed main(){ cin>>N>>M; fill(dist[0],dist[N],INF); for(int i=0;i<N;i++)dist[i][i]=0; for(int i=0;i<M;i++){ int a,b,c;cin>>a>>b>>c; chmin(dist[a-1][b-1],c); } for(int k=0;k<N;k++)for(int i=0;i<N;i++)for(int j=0;j<N;j++) if(dist[i][k]!=INF&&dist[k][j]!=INF)chmin(dist[i][j],dist[i][k]+dist[k][j]); for(int i=0;i<N;i++){ int sum=0; for(int j=0;j<N;j++)sum+=(dist[i][j]==INF?0:dist[i][j]); cout<<sum<<endl; } }