#include <fstream>
using namespace std;
ifstream g("dijkstra.in");
ofstream gg("dijkstra.out");
int n,m,mat[100][100],NMAX;
const int inf =1<<30;
void dijkstra(int x)
{
    int i,j,mini,k,ok;
    int viz[NMAX],d[NMAX],tata[NMAX];
    for(i=1;i<=n;i++)
    {
        d[i]=mat[x][i];
        tata[i]=x;
    }
    viz[x]=1; ok=1;
    while(ok==1)
    {
        mini=inf;
        for(i=1;i<=n;i++)
        {
            if(!viz[i]&&mini>d[i])
            {
                mini=d[i];
                k=i;
            }
        if(mini!=inf)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
            {
                if(viz[i]==0&&d[i]>d[k]+mat[k][i])
                {
                    d[i]=d[k]+mat[k][i];
                    tata[i]=k;
                }
            }
        }
        else ok=0;
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]!=inf) gg<<d[i]<<" ";
        else gg<<"0 ";
    }
 }
int main()
{
    int a,b,c;
    g>>n>>m;
    NMAX=n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            mat[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++)
    {
        g>>a>>b>>c;
        mat[a][b]=c;
    }
    dijkstra(1);
    g.close();
    gg.close();
    return 0;
}