#ifndef $
#define $

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#include <set>

using namespace std;

typedef vector< pair <int, int> >::iterator IT;
const int NMAX = 50005, INF = 0b01111111111111111111111111111111;
int n,m;
int d[NMAX];

vector < pair<int,int> > T[NMAX + 1];
set <int> h;
int bentvan[NMAX + 1];

int main()
{
    ifstream be("dijkstra.in");
    ofstream ki("dijkstra.out");
    be>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int from, to, cost;
        be>>from>>to>>cost;
        T[from].push_back(make_pair(to,cost));
    }

    for(int i = 2; i < n + 1; i++)
        d[i] = INF;
    d[1] = 0;
    h.insert(1);
    bentvan[1]++;
    while(!h.empty())
    {
        int now = *h.begin();
        h.erase(h.begin());
        bentvan[now]--;
        //cout<<now<<endl;

        for(IT it = T[now].begin(); it != T[now].end(); ++it)
        {
            int to = it -> first;
            int cost = it -> second;
            if(d[to] > d[now] + cost)
            {
                h.insert(to);
                h.erase(h.find(to));
                d[to] = d[now] + cost;
                h.insert(to);
                bentvan[to]++;
            }
        }
    }

    for(int i = 2; i<= n; i++)
    {
        if(d[i] == INF)
            d[i] = 0;
        ki<<d[i]<<" ";
    }

    return 0;
}

#endif