#include <fstream>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int dp[250001];
int v[250001][3];

int main()
{
    int n,m,nr=1,i,j,stg,k,c;
    cin>>n>>m;
    for(i=2;i<=n;i++){
        dp[i]=2000000;
    }
    dp[1]=0;
    for(i=1;i<=m;i++){
        cin>>v[i][1]>>v[i][2]>>v[i][3];
        if(v[i][1]==1)
            dp[v[i][2]]=v[i][3];
    }
    nr=0;stg=1;
    while(stg=1 && nr<n){
	    stg=0;
		for(k=1;k<=m;k++){
			i=v[k][1];j=v[k][2];c=v[k][3];
			if(dp[j]>dp[i]+c){
                dp[j]=dp[i]+c;
                stg=1;
            }
		}
		nr++;
	}
	for(i=2;i<=n;i++){
        if(dp[i]!=2000000) cout<<dp[i]<<" ";
        else cout<<"0 ";
	}
    return 0;
}