#include <bits/stdc++.h>

using namespace std;
class cmp
{
    public:
    bool operator ()(pair <int, int> &a, pair<int, int> &b)
    {
        return a.second>b.second;
    }
};
priority_queue < pair <int, int>, vector <pair<int, int>>, cmp> pq;
int n, m;
vector <pair <int, int>> graf[50001];
int dist[50001];
void initializare()
{
    int i;
    for (i = 2; i<=n; ++i)
        dist[i] = 2000000000;
}
int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    initializare();
    int y, i, j, x, nod, cost, d;
    for (i = 0; i<m; ++i)
    {
        fin >> x >> y >> d;
        graf[x].push_back (make_pair(y, d));
    }
    pq.push(make_pair(1, dist[1]));
    while (pq.size())
    {
        nod = pq.top().first;
        cost = pq.top().second;
        pq.pop();
        if (dist[nod] != cost)
            continue;
        for (auto x : graf[nod])
        {
            if (cost + x.second < dist[x.first])
            {
                dist[x.first] = cost+x.second;
                pq.push(make_pair(x.first, dist[x.first]));
            }
        }
    }
    for (i = 2; i<=n; ++i)
        {if (dist[i] != 2000000000)
            fout << dist[i] << " ";
        else fout << "0 ";}
    return 0;
}