#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
    int s=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') {
            w=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        s=s*10+c-'0';
        c=getchar();
    }
    x=s*w;
    return;
}
int n,m;
int u,v;
long long w;
long long dist[2010][2010];
inline void floyd() {
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    return ;
}
int main() {
    read(n),read(m);
    for(int i=1;i<=2000;i++){
		for(int j=1;j<=2000;j++){
			dist[i][j]=INT_MAX;
		}
	}
    for(int i=1;i<=2000;i++){
		dist[i][i]=0;
	}
    for(int i=1; i<=m; i++) {
        scanf("%d%d%lld",&u,&v,&w);
        dist[u][v]=min(dist[u][v],w);
    }
    floyd();
    for(int i=1;i<=n;i++){
    	if(dist[1][i]==INT_MAX){
			printf("-1");
			continue;
		}
		printf("%lld ",dist[1][i]);
	}
    return 0;
}

玄关