#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define nmax 50005
#define pq priority_queue
using namespace std;
int n, m, from, to, cost;
const int inf = 1e9 + 5;
struct graf
{
    int nod, dist;
    graf(const int &nod, const int &dist)
    {
        this->nod = nod, this->dist = dist;
    }
    bool operator <(const graf &other)const
    {
        return this->dist > other.dist;
    }
};
vector<vector<graf> >v[nmax];
pq<graf>q;
int dist[nmax];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int32_t main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        fin >> from >> to >> cost;
        v[from].push_back(make_pair(cost, to));
    }
    memset(dist, inf, sizeof dist);
    pq.push(make_pair(0, 1));
    while(!pq.empty())
    {
        int nod = pq.top().nod, dis = pq.top().dist;
        pq.pop();
        if(dist[nod] != inf)
        {
            continue;
        }
        dist[nod] = dis;
        for(auto& it : v[nod])
        {
            if(dist[it.nod] == inf)
            {
                pq.push(it.dist + dis, it.nod);
            }
        }
    }
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] == inf)
        {
            fout << 0 << " ";
        }
        else
        {
            fout << dist[i] << " ";
        }
    }
    return 0;
}