#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,c[5005][5005],s[5005],i,d[5005];
void cit(){
    int i,j,k,cost;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i!=j)
        c[i][j]=100000000;
    for(k=1;k<=m;k++){
        fin>>i>>j>>cost;
        c[i][j]=cost;
    }
}
void dijkstra(int r){
    int i,k,j,Min;
    for(j=1;j<=n;j++)
        d[j]=c[r][j];
    s[r]=1;
    for(k=1;k<=n-1;k++){
        Min=100000000;
        for(j=1;j<=n;j++)
            if(Min>d[j]&&s[j]==0){
                i=j;
                Min=d[j];
            }
        s[i]=1;
        for(j=1;j<=n;j++)
            if(d[j]>d[i]+c[i][j]){
                d[j]=d[i]+c[i][j];
            }
    }
}
int main()
{
    cit();
    dijkstra(1);
    for(i=1;i<=n;i++)
        if(i!=1)
            if(d[i]!=100000000)
            fout<<d[i]<<" ";
            else
                fout<<0<<" ";
    return 0;
}