#include <iostream>
#include <fstream>
#define Dmax 15000
#define inf 20005
using namespace std;
int n,m,a[Dmax][Dmax],t[Dmax]={0},d[Dmax],v[Dmax];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void citire()
{
    int i,j,x,y,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
    {
        if(i==j)
            a[i][j]=0;
        else
            a[i][j]=inf;
    }
    while(f>>x>>y>>c)
    {
        a[x][y]=c;
    }

}

void dijkstra(int x)
{
    int k,ok=1,mn,i,j;
    for(i=1;i<=n;i++)
    {
        d[i]=a[x][i];
        if(d[i]<inf)
            t[i]=x;
        v[i]=0;
    }
    v[x]=1;
    t[x]=0;

    while(ok)
    {
        mn=inf;
        for(i=1;i<=n;i++)
        {
            if(!v[i]&&d[i]<mn)
                {
                    k=i;
                    mn=d[i];
                }
        }
        if(mn==inf)
            ok=0;
        else
        {
            v[k]=1;
            for(i=1;i<=n;i++)
            if(!v[i]&&d[i]>d[k]+a[k][i])
            d[i]=d[k]+a[k][i];
            t[i]=k;
        }


    }


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

}


int main()
{
    citire();
    dijkstra(1);
    f.close();
    g.close();
    return 0;
}