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

using namespace std;

vector <pair<int ,int> > graf[60000];
vector <int> dist;
vector <int> prev;
int heap[60000];
int n,m,nod,dest,cost,k;

void interschimb (int x,int y){
    int t = heap[x];
    heap[x]=heap[y];
    heap[y]=t;
}

void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( dist[ heap[tata] ] > dist[ heap[what] ] )
        {
            prev[ heap[what] ] = tata;
            prev[ heap[tata] ] = what;

            interschimb(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( dist[ heap[f + 1] ] < dist[ heap[f] ] )
                    ++f;
        }
        else
            return;

        if ( dist[ heap[what] ] > dist[ heap[f] ] )
        {
            prev[ heap[what] ] = f;
            prev[ heap[f] ] = what;

            interschimb(what, f);

            what = f;
        }
        else
            return;
    }
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>nod>>dest>>cost;
        graf[nod].push_back(std::make_pair (dest,cost));
    }
    dist.push_back(0);dist.push_back(0);
    prev.push_back(0);prev.push_back(1);
    for(int i=2;i<=n;i++){
        dist.push_back(600000);
        prev.push_back(-1);
    }
    heap[++k]=1;
    while(k){
        int min = heap[1];
        interschimb(1, k);
        prev[ heap[1] ] = 1;
        --k;

        downheap(1);

        vector <pair<int ,int> >::iterator q=graf[min].begin();

        while ( q<graf[min].end() )
        {
            if ( dist[q->first] > dist[min] + q->second )
            {
                dist[q->first] = dist[min] + q->second;

                if ( prev[q->first] != -1 )
                    upheap( prev[q->first] );
                else
                {
                    heap[++k] = q->first;
                    prev[ heap[k] ] = k;
                    upheap( k );
                }
            }
            q++;
        }
    }
    for ( int i = 2; i <= n; ++i )
        fout<<(dist[i] == 600000 ? 0 : dist[i])<<' ';
    fout<<'\n';
    return 0;
}