//classic
#include <iostream>
#include <fstream>
using namespace std;
int M[2][10000][10000],Cost[50001],Parinte[50001],n,m;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void adancime(int nod)
{
    int i;
    for (i=1;i<=M[0][nod][0];i++)
    {
        if (M[1][nod][i]+Cost[nod]<Cost[M[0][nod][i]]||Cost[M[0][nod][i]]==0)
        {
            Parinte[M[0][nod][i]]=nod;
            Cost[M[0][nod][i]]=M[1][nod][i]+Cost[nod];
            adancime(M[0][nod][i]);
        }
    }
}
int main()
{
    f>>n>>m;
    int i,a,b,cost;
    for (i=1;i<=m;i++)
    {
        f>>a>>b>>cost;
        M[0][a][0]++;
        M[0][a][M[0][a][0]]=b;
        M[1][a][M[0][a][0]]=cost;
    }
    adancime(1);
    for (i=2;i<=n;i++) g<<Cost[i]<<" ";
}