#include <bits/stdc++.h>
#define ll long long
#define MAXN 50001

using namespace std;

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

vector<pair<int, int>> edges[MAXN];
vector<int> dist(MAXN, INT_MAX);

int main() {
    int n, m;
    fin >> n >> m;

    ///"creez graful"
    for(int i = 0; i < m; i++) {
        int node1, node2, length;
        fin >> node1 >> node2 >> length;
        edges[node1].push_back(make_pair(node2, length));
    }

    dist[1] = 0;

    ///prima data retin distanta si apoi numarul nodului
    set<pair<int,int>> sett;
    sett.insert(make_pair(0, 1));

    ///facem asta pana cand set-ul este gol, deci pana cand toate distantele sunt minime
    while(!sett.empty()) {
        int curr_node = sett.begin() -> second;
        int d = sett.begin() -> first;
        sett.erase(sett.begin());

        for(int i = 0; i < edges[curr_node].size(); i++) {
            int neighbour = edges[curr_node][i].first;
            int length = edges[curr_node][i].second;
            ///daca exista o cale mai scurta de a ajunge la "vecin"
            if(dist[neighbour] > dist[curr_node] + length) {
                ///daca distanta nu e egala cu INT_MAX, atunci este in set
                ///deci trebuie sa o stergem si sa inseram noua distanta
                if(dist[neighbour] != INT_MAX)
                    sett.erase(sett.find(make_pair(dist[neighbour], neighbour)));

                ///"schimbam distanta vecinului"
                dist[neighbour] = dist[curr_node] + length;
                sett.insert(make_pair(dist[neighbour], neighbour));
            }
        }
    }

    ///printam distantele pentru fiecare nod
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INT_MAX)
            dist[i] = 0;
        fout << dist[i] << ' ';
    }

    fin.close();
    fout.close();
}