#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int mat[5000][5000],viz[5000][5000],val[5000],exp[5000],mn,ind,n,m,x,y,c;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        mat[x][y]=c;
        viz[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        val[i]=INT_MAX;
    val[1]=0;
    for(int i=1;i<=n;i++)
    {
        mn=INT_MAX;
        for(int j=1;j<=n;j++)
            if(val[i]<mn && exp[i]==0)
            {
                ind=i;
                mn=val[i];
            }
        exp[ind]=1;
        for(int j=1;j<=n;j++)
        {
            if(val[ind]+mat[ind][j]<val[j] && viz[ind][j]!=0)
                {val[j]=val[ind]+mat[ind][j];}
        }
    }
    for(int i=2;i<=n;i++)
        if(val[i]==INT_MAX)
            fout<<0<<" ";
        else fout<<val[i]<<" ";
    return 0;
}