#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef pair<int,int> pii;


const int INF = 2000000000;
const int NMAX = 50002;
int N,M;
vector<int> Ad[NMAX];
vector<int> Cost[NMAX];

int d[NMAX];
bool in_h[NMAX];

void Read()
{
    fin>>N>>M;
    for(int i=1; i<=M; ++i)
    {
        int a,b,d;
        fin >> a>> b>>d;
        Ad[a].push_back(b);
        Cost[a].push_back(d);
    }
    fin.close();
}

void Do()
{
    priority_queue <pii, vector<pii>, greater<pii>> Heap;
    for(int i=1; i<=N; ++i)
        d[i]=INF;
    d[1]=0;
    int nod;
    Heap.push( make_pair(0,1) );

    while( !Heap.empty())
    {
        nod = Heap.top().second;
        Heap.pop();
        if( in_h[nod]) continue;
        else in_h[nod] = true;

        for(int i = 0; i < Ad[nod].size(); ++i)
        {
            int w = Ad[nod][i];

            if(d[nod] + Cost[nod][i] < d[w])
            {
                d[w] = d[nod] + Cost[nod][i];
                Heap.push(make_pair( d[w],w ));
            }
        }
    }
    for(int i=2; i<=N; ++i)
        if(d[i]== INF)
            fout<<0<<" ";
        else fout<<d[i]<<" ";

}

int main()
{
    Read();
    Do();
    return 0;
}