#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const long long inf = 1e9+1;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX = 50001;
int start;
ll dist[NMAX];//dist[i]=distanta minima de la nodul de start la nodul i
struct elem {
    int nod;
    int cost;
    elem(int nodCrt, int c) :nod(nodCrt), cost(c) {};
};
vector<vector<elem>>graph;


struct alese {
    bool operator ()(pair<int, ll> a, pair<int, ll> b) {
        return dist[a.first] > dist[b.first];
    }
};
void dijkstra(int n) {
    priority_queue<pair<int,ll>, vector<pair<int, ll>>, alese>pq;

    pq.push({1,0});
    pair<int,ll> crt;

    ll alt;
    while (!pq.empty())
    {
        crt = pq.top();
        pq.pop();
        if (dist[crt.first] == crt.second) {
            for (auto v : graph[crt.first]) {
                alt = dist[crt.first] + v.cost;
                if (alt < dist[v.nod]) {
                    dist[v.nod] = alt;
                    pq.push(make_pair(v.nod, alt));
                }
            }
        }
    }
    return;

}

int main() {
    int n, m;
    fin >> n >> m;
    graph.resize(n + 1);
    int firstNod, secondNod, cost;
    for (int i = 0; i < m; ++i) {
        fin >> firstNod >> secondNod >> cost;
        graph[firstNod].push_back(elem(secondNod, cost));//nu e si invers pentru ca zice ca este "graf orientat"
    }
    for (int i = 0; i <= n; ++i) {
        dist[i] = inf;
    }
    dist[1] = 0;//distanta de la nodul de start la el insusi este 0
    dijkstra(n);
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == inf) {
            fout << 0 << " ";
        }
        else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}