#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int maxi = 20000;

int n,m,k;

long long int a[5000][5000],d[50000],viz[50000],coada[50000];

void cit()
{
    int x,y,cost;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                a[i][j]=maxi;
            }
            else
            {
                a[i][j]=0;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[x][y] = cost;
    }
}

void dijkstra(int nod)
{
    int k,mini,j;
    for(int i=1;i<=n;i++)
    {
        d[i]=a[nod][i];
        if(i!=nod && d[i]!=maxi)
        {
            coada[i]=nod;
        }
    }
    viz[nod]=1;
    for(k=1;k<n;k++)
    {
        mini=maxi;
        for(int i=1;i<=n;i++)
        {
            if(viz[i] == 0 && d[i] < mini)
            {
                mini = d[i];
                j=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(viz[i] == 0 && d[i] > d[j] + a[j][i])
            {
                d[i] = d[j] + a[j][i];
                coada[i] = j;
            }
        }
        viz[j]=1;
    }
}

void afis()
{
    for(int i=2;i<=n;i++)
    {
        drum(i);
        fout<<d[i]<<" ";
    }
}

int main()
{
    cit();
    dijkstra(1);
    afis();
    return 0;
}