#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
int inf = 0x3f3f3f;
int main()
{   int a, b, c;
    f >> n >> m;
    vector<pair<long long, int>> graf[n+1];
    vector<long long>cost((n+1),inf);
    priority_queue<pair<long long, int>>s;
    vector<bool>viz(n+1);
    for (int i=1; i<=m; i++)
        { f >> a >> b >> c;
          graf[a].push_back({c, b});
        }
    s.push({0, 1});
    cost[1] = 0;
    while(!s.empty())
        {
            pair<long long, int> smallest = s.top();
            s.pop();
            if(viz[smallest.second]) continue;
            viz[smallest.second] = 1;
            for(int i=0; i<graf[smallest.second].size(); i++)
                {
                    int node = graf[smallest.second][i].second;
                    int val = graf[smallest.second][i].first;
                    if(-smallest.first + val < cost[node])
                        {
                            cost[node] = -smallest.first + val;
                            s.push({-cost[node], node});
                        }
                }
        }
    for (int i=2; i<=n; i++) (cost[i] == inf) ? g << 0 << ' ' : g << cost[i] << ' ';

    return 0;
}