#include <iostream>
#include <fstream>
#include <unordered_set>
#include <vector>
#include <chrono>

#define infi 0x3f3f3f3f

using namespace std;

struct graf {
    int dest, cost;
};

int m, n, c;
graf e;
vector<unordered_set<int>> buckets;
vector<vector<graf>> adj;
vector<int> d;
int pos, final;

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

void read_graph(void) {
    int i;
    fin >> n >> m;

    vector<graf> v;
    adj.resize(n, v);

    c = 0;

    int a, b, c;
    for (i = 0; i < m; ++i) {
        fin >> a >> b >> c;
        --a;
        --b;
        e.dest = b, e.cost = c;
        adj[a].push_back(e);

        if (c > c)
            c = c;
    }
}

int next_bucket() {
    for (int i = 0; i < c + 1; ++i) {
        int k = (pos + i) % (c + 1);

        if (!buckets[k].empty())
            return k;
    }

    return -1;
}

void relax_neighbours(int u) {
    int n = adj[u].size();

    for (int i = 0; i < n; ++i) {
        graf e = adj[u][i];
        int v = e.dest;
        int len = e.cost;

        if (d[v] > d[u] + len) {
            if (d[v] != infi) {
                int t = d[v] % (c + 1);
                buckets[t].erase(v);
            }

            d[v] = d[u] + len;
            int t = d[v] % (c + 1);
            buckets[t].insert(v);
        }
    }
}

void dijkstra(void) {
    unordered_set<int> l;
    buckets.resize(c + 1, l);

    d.resize(n, infi);
    d[0] = pos = 0;
    buckets[0].insert(0);
    final = n;

    while (final > 0) {
        int k = next_bucket();
        if (k == -1)
            break;

        while (!buckets[k].empty()) {
            int u = *buckets[k].begin();
            buckets[k].erase(u);
            relax_neighbours(u);
            --final;
        }
        pos = (k + 1) % (c + 1);
    }
}

int main() {
    auto start = chrono::high_resolution_clock::now();

    read_graph();
    dijkstra();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "execution time: " << duration << " milliseconds" << endl;

    for (int i = 0; i < n; i++) {
        if (d[i] != infi)
            fout << d[i] << endl;
        else
            fout << 0 << endl;
    }

    return 0;
}