#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>> g[50005];
priority_queue<pair<int, int>> pq;

int viz[50005];
const int INF = (1e9);

int main()
{
    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, c; in >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
        //g[y].push_back(make_pair(x, c));
    }

    for(int i = 0; i <= n+1; i++)
    {
        viz[i] = INF;
    }

    viz[1] = 0;
    pq.push(make_pair(0, 1));

    while(!pq.empty())
    {
        auto cnt = pq.top(); pq.pop();
        int cnt_cost = 1LL * cnt.first * (-1);
        int cnt_node = cnt.second;

        if(viz[cnt_node] != cnt_cost) continue;

        for(auto vec : g[cnt_node])
        {
            if(viz[vec.first] > cnt_cost + vec.second)
            {
                viz[vec.first] = cnt_cost + vec.second;
                pq.push(make_pair(-viz[vec.first], vec.first));
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        if(viz[i] == INF) out << "0 ";
        else out << viz[i] << " ";
    }
}