#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#define dim 50005

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

vector < pair < int,int > > vec[dim];
vector < pair < int,int > > ::iterator it;
set < pair < int,int > > heap;
int INF = 0x3f3f3f3f,d[dim];

int main()
{
    int n,m,i,x,y,c,nod,nou_nod;
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        vec[x].push_back(make_pair(y,c));
    }

    memset(d , INF , sizeof d);
    d[1] = 0;
    heap.insert(make_pair(0,1));
    while(not heap.empty())
    {
        c = heap.begin() -> first;
        nod = heap.begin() -> second;
        heap.erase(heap.begin());

        for(it = vec[nod].begin(); it != vec[nod].end(); it++)
        {
            nou_nod = it -> first;
            c = it -> second;
            if(d[nou_nod] > d[nod] + c)
            {
                if(d[nou_nod] != INF)
                {
                    heap.erase(heap.find(make_pair(d[nou_nod],nou_nod)));
                }
                d[nou_nod] = d[nod] + c;
                heap.insert(make_pair(d[nou_nod],nou_nod));
            }
        }
    }
    for ( i = 2; i <= n; ++i)
    {
        if (d[i] == INF)
        {
            d[i] = 0;
        }
        g <<  d[i] << ' ';
    }
    return 0;
}