#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> pll;
int main() {
int n, m;
// n = cities, m = flights
cin >> n >> m;
vector<pll> adj[n+1];
for (int i=0; i<m; i++) {
long long a, b, c;
// flight from a to b with cost c
cin >> a >> b >> c;
adj[a].push_back( {b, c} );
}
vector<long long> dist(n+1, LLONG_MAX);
// minimum priority queue
priority_queue< pll , vector<pll>, greater<pll> > pq; // smallest item first
// {dist, nodeNumber}
pq.push( {0, 1} );
while(!pq.empty()) {
pll x = pq.top();
pq.pop();
long long d = x.first , cur = x.second;
if (d >= dist[cur]) continue; // if (vis[cur]) continue
dist[cur] = d; // vis[cur] = true
// for each adjacent node of cur
for (pll x: adj[cur]) {
long long v = x.first, c = x.second;
long long newDist = d + c;
if (newDist >= dist[v]) continue;
pq.push({newDist, v});
}
}
for (int i=1; i<=n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8bG9uZyBsb25nLCBsb25nIGxvbmc+IHBsbDsKCmludCBtYWluKCkgewogICAgaW50IG4sIG07IAogICAgLy8gbiA9IGNpdGllcywgbSA9IGZsaWdodHMKICAgIGNpbiA+PiBuID4+IG07CgogICAgdmVjdG9yPHBsbD4gYWRqW24rMV07CgogICAgZm9yIChpbnQgaT0wOyBpPG07IGkrKykgewogICAgICAgIGxvbmcgbG9uZyBhLCBiLCBjOwogICAgICAgIC8vIGZsaWdodCBmcm9tIGEgdG8gYiB3aXRoIGNvc3QgYwogICAgICAgIGNpbiA+PiBhID4+IGIgPj4gYzsKICAgICAgICBhZGpbYV0ucHVzaF9iYWNrKCB7YiwgY30gKTsKICAgIH0KCiAgICB2ZWN0b3I8bG9uZyBsb25nPiBkaXN0KG4rMSwgTExPTkdfTUFYKTsKCiAgICAvLyBtaW5pbXVtIHByaW9yaXR5IHF1ZXVlCiAgICBwcmlvcml0eV9xdWV1ZTwgcGxsICwgdmVjdG9yPHBsbD4sIGdyZWF0ZXI8cGxsPiA+IHBxOyAvLyBzbWFsbGVzdCBpdGVtIGZpcnN0CiAgICAvLyB7ZGlzdCwgbm9kZU51bWJlcn0KICAgIHBxLnB1c2goIHswLCAxfSApOyAKCiAgICB3aGlsZSghcHEuZW1wdHkoKSkgewogICAgICAgIHBsbCB4ID0gcHEudG9wKCk7CiAgICAgICAgcHEucG9wKCk7CiAgICAgICAgbG9uZyBsb25nIGQgPSB4LmZpcnN0ICwgY3VyID0geC5zZWNvbmQ7CgogICAgICAgIGlmIChkID49IGRpc3RbY3VyXSkgY29udGludWU7IC8vIGlmICh2aXNbY3VyXSkgY29udGludWUKICAgICAgICBkaXN0W2N1cl0gPSBkOyAvLyB2aXNbY3VyXSA9IHRydWUKCiAgICAgICAgLy8gZm9yIGVhY2ggYWRqYWNlbnQgbm9kZSBvZiBjdXIKICAgICAgICBmb3IgKHBsbCB4OiBhZGpbY3VyXSkgewogICAgICAgICAgICBsb25nIGxvbmcgdiA9IHguZmlyc3QsIGMgPSB4LnNlY29uZDsKICAgICAgICAgICAgbG9uZyBsb25nIG5ld0Rpc3QgPSBkICsgYzsKICAgICAgICAgICAgaWYgKG5ld0Rpc3QgPj0gZGlzdFt2XSkgY29udGludWU7CiAgICAgICAgICAgIHBxLnB1c2goe25ld0Rpc3QsIHZ9KTsKICAgICAgICB9CiAgICB9CgogICAgZm9yIChpbnQgaT0xOyBpPD1uOyBpKyspIHsKICAgICAgICBjb3V0IDw8IGRpc3RbaV0gPDwgIiAiOwogICAgfQogICAgY291dCA8PCBlbmRsOwp9