#include <fstream>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

#define oo 0x3f3f3f3f

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

int n, m;
vector<vector<pair<int, int>>> graph;
vector<int> dist;

void read() {
    f>>n>>m;
    int x, y, z;

    graph.resize(n + 1, vector<pair<int, int>>());
    dist.resize(n + 1, oo);

    for(int i = 0;i < m;++i) {
        f>>x>>y>>z;
        graph[x].push_back(make_pair(y, z));
    }
    f.close();
}

void solve() {
    dist[1] = 0;
    set<pair<int, int>> dij;
    dij.insert(make_pair(0, 1));

    while(!dij.empty()) {
        int cost = dij.begin()->first;
        int node = dij.begin()->second;
        dij.erase(dij.begin());

        for(const auto& [ngh, d] : graph[node]) {
            if(dist[ngh] > dist[node] + d) {
                if(dist[ngh] != oo) {
                    dij.erase(dij.find(make_pair(dist[ngh], ngh)));
                }
                dist[ngh] = dist[node] + d;
                dij.insert(make_pair(dist[ngh], ngh));
            }
        }
    }

    for(int i = 1;i <= n;++i) {
        g<<dist[i]<<" ";
    }
    g.close();
}

int main() {
    read();
    solve();

    return 0;
}