#include <bits/stdc++.h>
#define MAXN 50010
using namespace std;

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

vector<pair<int,int> > v[MAXN];
int d[MAXN];
int n,m;

int main()
{
    fin>>n>>m;
    int from, to, cost;
    for(int i=1;i<=m;i++)
    {
        fin>>from>>to>>cost;
        v[from].push_back(make_pair(to, cost));
    }
    for(int i=1;i<=n;i++)
        d[i] = MAXN;
    d[1] = 0;
    set<pair<int, int> > h;
    h.insert(make_pair(0, 1));
    while(!h.empty())
    {
        int node = h.begin()->second;
        int dist = h.begin()->first;
        h.erase(h.begin());

        for(auto it:v[node])
        {
            int to = it.first;
            int cost = it.second;
            if(d[to] > d[node] + cost)
            {
                if(d[to] != MAXN)
                {
                    h.erase(h.find(make_pair(d[to], to)));
                }
                d[to] = d[node] + cost;
                h.insert(make_pair(d[to], to));
            }
        }
    }
    for(int i=2;i<= n; i++){
        if(d[i] == MAXN)
            fout<<0;
        else
            fout<<d[i];
        if(i!=n)
            fout<<' ';
    }
    fout<<'\n';

    return 0;
}