#include<fstream>
#include<iostream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[50][50],s[50],t[50],n,x,minim,poz,m,k,cost;
const int inf=30000;
void drum(int nod)
{
    if(t[nod])
    drum(t[nod]);
    g<<nod<<" ";
}
int main()
{
    int i,j,d[50];
    f>>n>>m;
    for(i=1;i<=n;i++)
        d[i]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        a[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>cost;
        a[j][k]=cost;
    }
    s[1]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=a[1][i];
        if(i!=1)
        if(d[i]<inf)
        t[i]=1;
    }
    for(i=1;i<=n;i++)
    {
        minim=inf;
        for(j=1;j<=n;j++)
        if(s[j]==0)
        if(d[j]<minim)
        {
            minim=d[j];
            poz=j;
        }
        s[poz]=1;
        for(j=1;j<=n;j++)
        if(s[j]==0)
        if(d[j]>d[poz]+a[poz][j])
        {
            d[j]=d[poz]+a[poz][j];
            t[j]=poz;
        }
    }
    for(i=2;i<=n;i++)
    g<<d[i]<<" ";
return 0;
}