#include <iostream>
#include <fstream>
#include <vector>

#define INFINIT 2000000000

using namespace std;

vector <long> G[50005];
vector <long> C[50005];
long N, D[50005];
bool V[50005];

void Read ()
{
    ifstream fin ("dijkstra.in");
    long M, i, X, Y, Z;
    fin >> N >> M;
    for (i=0; i<M; i++)
    {
        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++)
    {
        fout << D[i] << " ";
    }
    fout << "\n";
    fout.close ();
}

inline long Min (long a, long b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

void Dijkstra (long Start)
{
    unsigned long i;
    long NCurent=Start, NNext, MinCurent, Valid=1;
    for (i=1; i<=N; i++)
    {
        D[i]=INFINIT;
    }
    D[Start]=0;
    while (Valid==1)
    {
        MinCurent=INFINIT;
        Valid=0;
        for (i=1; i<=N; i++)
        {
            if ((V[i]==false)&&(D[i]<MinCurent))
            {
                NCurent=i;
                MinCurent=D[i];
                Valid=1;
            }
        }
        for (i=0; i<G[NCurent].size (); i++)
        {
            D[G[NCurent][i]]=Min (D[G[NCurent][i]], D[NCurent]+C[NCurent][i]);
        }
        V[NCurent]=true;
    }
}

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