#include <bits/stdc++.h>
#define ff first
#define ss second
//#define int long long   //Far too often i've had wrong answers because of int overflow.

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

const string file = "dijkstra";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;

int n, m;
vector< vector<pi> > graph;
vi dist;

signed main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    graph.resize(n);
    dist.resize(n, inf);
    for (int i = 0; i < m; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        --a, --b;
        graph[a].push_back(make_pair(b, c));
    }
    auto comp = [](int a, int b){
        if (dist[a] != dist[b])
            return dist[a] < dist[b];
        return a < b;
    };
    set<int, decltype(comp)> q(comp);
    dist[0] = 0;
    q.insert(0);
    while(!q.empty()){
        int nod = *q.begin();
        q.erase(q.begin());
        for (auto neighbor : graph[nod])
            if (dist[nod]+neighbor.ss < dist[neighbor.ff]){
                auto it = q.find(neighbor.ff);
                if (it != q.end())
                    q.erase(it);
                dist[neighbor.ff] = dist[nod]+neighbor.ss;
                q.insert(neighbor.ff);
            }
    }
    for (int i = 1; i < n; ++i)
        fout << dist[i] << " ";
    return 0;
}