# include <iostream>
# include <fstream>
# include <string.h>
# define nmax 5000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int v[nmax], d[nmax], a[nmax][nmax], n, m;

void dijk()
{
    memset(d, '5', sizeof(d));
    v[1]=1;
    int min=9999, pmin;

    int i;
    for(i=1; i<=n; i++)
    {
        if(a[1][i]!=0 && v[i]==0)
            d[i]=a[1][i];
    }
    int k;
    for(k=1; k<n; i++)
    {
        min=9999;
        for(i=2; i<=n; i++)
        {
            if(min>d[i] && v[i]==0)
            {
                min=d[i];
                pmin=i;
            }
        }
        if(min==9999)
            break;
        v[pmin]=1;

        for(i=1; i<=n; i++)
        {
            if(v[i]==0 && d[i]>d[pmin]+a[pmin][i] && a[pmin][i])
                d[i]=d[pmin]+a[pmin][i];
        }
    }

}

int main()
{
    int i,j,x,y,z;
    f>>n>>m;

    for(i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }

    dijk();

    for(i=2; i<=n; i++)
        g<<d[i]<<" ";

    f.close();
    g.close();

    return 0;
}