#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 5e4 + 5;
const int maxm = 25e4 + 5;

#define vec first
#define cst second

vector < pair <int, int> > v[maxn];

struct cmp  {
    bool operator()  (pair <int, int> a, pair <int, int> b)  {
        return a.cst > b.cst;
    }
};

priority_queue <pair <int, int>, vector <pair <int, int> > , cmp> pq;

int d[maxn];
const int INF = 1e9;

int main()  {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for(int i = 1;i <= m;i++)  {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    for(int i = 1;i <= n;i++)
        d[i] = INF;
    pq.push({1, 0});
    while(!pq.empty())  {
        pair <int, int> nn = pq.top();
        pq.pop();
        int nod, cst;
        nod = nn.first, cst = nn.second;
        if(d[nod] != INF)
            continue;
        d[nod] = cst;
        for(auto x : v[nod])  {
            int vec, cst1;
            vec = x.vec;
            cst1 = x.cst;
            pq.push({vec, cst1 + cst});
        }
    }
    for(int i = 2;i <= n;i++)
        cout << d[i] << " ";
    return 0;
}