#include <iostream>
#include <fstream>
#include <climits>
#define Nmax 20001

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

int n, m;
int a[Nmax][Nmax], viz[Nmax];
int d[Nmax];

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        a[x][y]=z;
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int dmin=INT_MAX, nr=-1;
        for(int j=1;j<=n;j++)
        {
            if(viz[j]==0 && dmin>d[j])
            {
                dmin=d[j];
                nr=j;
            }
        }
        for(int j=1;j<=n && nr!=-1;j++)
        {
            if(viz[j]==0 && a[nr][j]!=0)
            {
                d[j]=min(d[j], d[nr]+a[nr][j]);
            }
        }
        viz[nr]=1;
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INT_MAX)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    return 0;
}