#include <iostream>
#include <fstream>
using namespace std;
int final,inceput,n,k,i,i1,m[1000][1000],d[1000],t[1000],m1;
void dijkstra(int n,int k, int m[][1000],int v[],int v1[])
{
    int kd,i,nodmn,mn,vv[1000];
    for (i=1;i<=n;i++)
        {vv[i]=0;
        v[i]=m[k][i];
        v1[i]=k;}
    vv[k]=1;
    kd=0;
    while (kd<n-1)
    {
        kd++;

        mn=2000000000;
        for (i=1;i<=n;i++)
            if ((v[i]<mn)&&(vv[i]==0))
            {
                nodmn=i;
                mn=v[i];
            }

        vv[nodmn]=1;
        for (i=1;i<=n;i++)
        if (v[i]>v[nodmn]+m[nodmn][i])
            {
                v[i]=v[nodmn]+m[nodmn][i];
                v1[i]=nodmn;
            }
    }
}
int main(void)
{
    FILE * f;
    f=fopen("dijkstra.in","r");
    ofstream g("dijkstra.out");
    fscanf(f,"%d%d",&n,&m1);
    for (i=1;i<=n;i++)
    for (i1=1;i1<=n;i1++)
        m[i][i1]=2000000000;
    for (i=1;i<=m1;i++)
    {
        fscanf(f,"%d%d%d",&inceput,&final,&i1);
        m[inceput][final]=i1;
    }
    dijkstra(n,1,m,d,t);
    for (i=2;i<=n;i++)
    if (d[i]==2000000000)
        g<<"0 ";
    else
        g<<d[i]<<' ';
    g.close();
    return 0;
}