#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
using namespace std;

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

priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > Q;
vector< vector< pair<int, int> > > vecini;
vector< long long > dist;
vector<bool>explorat;

int main() {
    int n, m;
    fin >> n >> m;
    vecini.resize(n + 1);
    dist.resize(n + 1);
    explorat.resize(n + 1);
    int a, b, w;
    while(m --) {
        fin >> a >> b >> w;
        vecini[a].push_back(make_pair(b, w));
    }
    Q.push(make_pair(0, 1));
    dist[1] = 0;
    explorat[1] = 1;
    while(!Q.empty()) {
        auto x = Q.top();
        Q.pop();
        if (explorat[x.second] && dist[x.second] < x.first) continue;
        for (auto k : vecini[x.second])
        {
            if (!explorat[k.first] || dist[k.first] > dist[x.second] + k.second)
            {
                explorat[k.first] = true;
                dist[k.first] = dist[x.second] + k.second;
                Q.push(make_pair(dist[k.first], k.first));
            }
        }
    }
    for(int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
}