#include <fstream>
#define inf 1001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,z,a[10001][10001],D[100001],T[100001],p,mi,k;
bool sel[100001];
void load()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if(i==j) a[i][j]=0; else a[i][j]=inf;
    for(int i=1;i<=m;i++)
        {
            f>>x>>y>>z;
            a[x][y]=z;
        }
}
void dijkstra(int p)
{
    D[p]=0;
    for(int i=1;i<=n;i++)
    {
        mi=inf;
        for(int j=i;j<=n;j++)
            if(!sel[j] && D[j]<mi)
            {
                mi=D[j];
                k=j;
        sel[k]=true;
            }
        for(int q=1;q<=n;q++)
            if(!sel[q] && D[q]>D[k]+a[k][q]){
            D[q]=D[k]+a[k][q];
            T[q]=k;
            }
    }
}
int main()
{
    load();
    for(int i=1;i<=n;i++)
    {
        D[i]=inf;
        sel[i]=false;
        T[i]=0;
    }
    dijkstra(2);
    for(int i=1;i<=n;i++)
        g<<D[i]<<" ";
    return 0;
}