#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const long Infinit=2000000005;
vector <long> G[50005];
vector <long> C[50005];
long N, D[50005], Heap[50005], P[50005], NH;

void Read ()
{
    FILE *fin = fopen ("dijkstra.in", "r");
    long M, i, X, Y, Z;
    fscanf (fin, "%ld%ld", &N, &M);
    for (i=0; i<M; i++)
    {
        fscanf (fin, "%ld%ld%ld", &X, &Y, &Z);
        G[X].push_back (Y);
        C[X].push_back (Z);
    }
    fclose (fin);
}

void Type ()
{
    FILE *fout = fopen ("dijkstra.out", "w");
    unsigned long i;
    for (i=2; i<=N; i++)
    {
        if (D[i]==Infinit)
        {
            D[i]=0;
        }
        fprintf (fout, "%ld ", D[i]);
    }
    fprintf (fout, "\n");
    fclose (fout);
}

void Sift (long X)
{
    long Aux, S=X;
    if (2*X<=NH)
    {
        S=2*X;
    }
    if ((2*X+1<=NH)&&(D[Heap[S]]>D[Heap[2*X+1]]))
    {
        S++;
    }
    if (D[Heap[S]]<D[Heap[X]])
    {
        Aux=P[Heap[X]];
        P[Heap[X]]=P[Heap[S]];
        P[Heap[S]]=Aux;
        Aux=Heap[X];
        Heap[X]=Heap[S];
        Heap[S]=Aux;
        Sift (S);
    }
}

void Percolate (long X)
{
    long Aux, F=X/2;
    if ((D[Heap[F]]>D[Heap[X]])&&(F>0))
    {
        Aux=P[Heap[X]];
        P[Heap[X]]=P[Heap[F]];
        P[Heap[F]]=Aux;
        Aux=Heap[X];
        Heap[X]=Heap[F];
        Heap[F]=Aux;
        Percolate (F);
    }
}

void Insert (long X)
{
    Heap[++NH]=X;
    P[Heap[NH]]=NH;
    Percolate (NH);
}

void Delete (long X)
{
    Heap[1]=Heap[NH--];
    P[Heap[1]]=1;
    Sift (1);
}

void Dijkstra (long Start)
{
    unsigned long i;
    long NCurent;
    for (i=1; i<=N; i++)
    {
        P[i]=-1;
        D[i]=Infinit;
    }
    D[Start]=0;
    P[Start]=1;
    Heap[++NH]=Start;
    while (NH>0)
    {
        NCurent=Heap[1];
        Delete (1);
        for (i=0; i<G[NCurent].size (); i++)
        {
            if (P[G[NCurent][i]]==-1)
            {
                D[G[NCurent][i]]=D[NCurent]+C[NCurent][i];
                Insert (G[NCurent][i]);
            }
            if (D[G[NCurent][i]]>D[NCurent]+C[NCurent][i])
            {
                D[G[NCurent][i]]=D[NCurent]+C[NCurent][i];
                Percolate (P[G[NCurent][i]]);
            }
        }
    }
}

int main()
{
    Read ();
    Dijkstra (1);
    Type ();
    return 0;
}