#include <algorithm>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#ifdef INFOARENA
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
#else
    #define in cin
    #define out cout
#endif
#define FORIT(it,v) for(typeof((v).begin())it=(v).begin();it!=(v).end();++it)
const int MAX_N = 50100;
const int INF = 1 << 30;

int N, M;
vector<pair<int, int> > graph[MAX_N];
vector<vector<int> > d;
int cost[MAX_N];
int max_edge = 0;
bool visited[MAX_N];

void read_input();
void solve();
void print_output();

int main() {
    read_input();
    solve();
    print_output();
    return 0;
}

void read_input() {
    in >> N >> M;
    for (int i = 1, a, b, c; i <= M; ++i) {
        in >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        max_edge = max(max_edge, c);
    }
}

void solve() {
    d.resize(++max_edge);
    int used_nodes = 0;
    int source = 1;
    d[0].push_back(source);
    fill(cost, cost + N + 1, INF);
    cost[source] = 0;

    for (int i = 0; used_nodes < N; ++i) {
        int dist = i % max_edge;
        while (!d[dist].empty()) {
            int node = d[dist].back();
            d[dist].pop_back();
            if (visited[node] == true) continue;
            visited[node] = true;
            ++used_nodes;

            FORIT (it, graph[node]) {
                if (!visited[it->first]) {
                    if (cost[node] + it->second < cost[it->first]) {
                        cost[it->first] = cost[node] + it->second;
                        d[cost[it->first] % max_edge].push_back(it->first);
                    }
                }
            }
        }
    }
}

void print_output() {
    for (int i = 2; i <= N; ++i) {
        out << (cost[i] == INF ? 0 : cost[i]) << ' ';
    }
}