# include <iostream>
# include <fstream>
# include <vector>
# include <string.h>
# define maxn 50000
using namespace std;

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

int n,m,d[maxn],t[maxn],v[maxn];
int c[5000][5000];
void dijk()
{
    int min,pmin,nrv=1,i;
    for(i=1; i<=n; i++)
    {
        if(c[1][i]!=0)
        {
            d[i]=c[1][i];
            t[i]=1;
        }
        else
        {
            d[i]=maxn;
        }
    }
    v[1]=1;
    while(nrv<=n)
    {
        min=maxn;
        for(i=1; i<=n; i++)
        {
            if(min>d[i] && v[i]==0)
            {
                min=d[i];
                pmin=i;
            }
        }
        if(min==maxn)
            break;
        v[pmin]=1;
        for(i=1; i<=n; i++)
        {
            if(v[i]==0 && c[pmin][i]!=0 && d[i]>min+c[pmin][i])
            {
                d[i]=min+c[pmin][i];
                t[i]=pmin;
            }
        }
        nrv+=1;

    }
}

int main()
{
    f>>n>>m;
    int i,x,y,z;
    //memset(c,5, sizeof(c));
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
    }
    dijk();

    for(i=2; i<=n; i++)
    {
        cout<<d[i]<<" ";
    }

    return 0;
}