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

#define Infinit 2000000000
#define NMax 50005
#define v first
#define c second

using namespace std;

vector < pair <int, int> > G[NMax];
int N, H[NMax], NH, Poz[NMax], D[NMax];

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

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

inline void Swap (int X, int Y)
{
    int Aux;
    Aux=Poz[H[X]];
    Poz[H[X]]=Poz[H[Y]];
    Poz[H[Y]]=Aux;
    Aux=H[X];
    H[X]=H[Y];
    H[Y]=Aux;
}

void Percolate (int X)
{
    int Father=X/2;
    while (Father>0)
    {
        if (D[H[X]]<D[H[Father]])
        {
            Swap (X, Father);
            X=Father;
            Father=X/2;
        }
        else
        {
            return;
        }
    }
}

void Sift (int X)
{
    int Son=2*X;
    while (Son<=NH)
    {
        if (Son+1<=NH && D[H[Son+1]]<D[H[Son]])
        {
            ++Son;
        }
        if (D[H[X]]>D[H[Son]])
        {
            Swap (X, Son);
            X=Son;
            Son=2*X;
        }
        else
        {
            return;
        }
    }
}

void Delete (int X)
{
    Swap (X, NH);
    --NH;
    Sift (X);
}

void Initialize (int Start)
{
    NH=N;
    for (int i=1; i<=N; ++i)
    {
        D[i]=Infinit;
        H[i]=Poz[i]=i;
    }
    D[Start]=0;
    Swap (1, Start);
}

void Dijkstra (int Start)
{
    Initialize (Start);
    while (NH>0)
    {
        int X=H[1];
        Delete (1);
        for (unsigned i=0; i<G[X].size (); ++i)
        {
            int V=G[X][i].v, C=G[X][i].c;
            if (D[X]+C<D[V])
            {
                D[V]=D[X]+C;
                Percolate (Poz[V]);
            }
        }
    }
}

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