#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
struct Edge {
    int to, w;
};

vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p,int n) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                }
                else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}
int n, m, x, y, z;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    adj.resize(n+1);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        x--; y--;
        adj[x].push_back({ y,z });
    }
    vector<int> ans, p;
    shortest_paths(0, ans, p, n);
    for (int i = 1; i < ans.size(); i++)
    {
        if (ans[i] != INF)
            cout << ans[i];
        else cout << '0';
        cout << ' ';
    }
    return 0;
}