#include <fstream>
#include <vector>

using namespace std;

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

void Read ()
{
    ifstream fin ("dijkstra.in");
    long M, X, Y, Z;
    fin >> N >> M;
    for (; M>0; --M)
    {
        fin >> X >> Y >> Z;
        G[X].push_back (Y);
        C[X].push_back (Z);
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("dijkstra.out");
    unsigned long i;
    for (i=2; i<=N; ++i)
    {
        if (D[i]==Infinit)
        {
            D[i]=0;
        }
        fout << D[i] << " ";
    }
    fout << "\n";
    fout.close ();
}

inline void Swap (long X, long Y)
{
    long Aux;
    Aux=P[Heap[X]];
    P[Heap[X]]=P[Heap[Y]];
    P[Heap[Y]]=Aux;
    Aux=Heap[X];
    Heap[X]=Heap[Y];
    Heap[Y]=Aux;
}

void Sift (long X)
{
    long S=X<<1;
    while (S<=NH)
    {
        if (((X<<1)+1<=NH)&&(D[Heap[S]]>D[Heap[(X<<1)+1]]))
        {
            S++;
        }
        if (D[Heap[S]]<D[Heap[X]])
        {
            Swap (X, S);
            X=S;
            S=X<<1;
        }
        else
        {
            return;
        }
    }
}

void Percolate (long X)
{
    long F=X>>1;
    while (F)
    {
        if ((D[Heap[F]]>D[Heap[X]])&&(F>0))
        {
            Swap (X, F);
            X=F;
            F=X>>1;
        }
        else
        {
            return;
        }
    }
}

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

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

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;
}