#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

const int N = 300010;
const int NN = 100100;
const long long inf = (1LL<<60);

int n, m, s, d, a[N], b[N], c[N], k;
long long sum, dist[NN];
vector<pair<int, int> > v[NN];
priority_queue<pair<long long, int> > h;

void dij() {
    int i;

    for(i = 1; i <= n; ++i)
        dist[i] = inf;

    dist[d] = 0;
    h.push(pair<long long, int>(0, d));

    while(!h.empty()) {
        long long di = h.top().first;
        int el = h.top().second;
        h.pop();

        if(dist[el] != di)
            continue;

        for(vector<pair<int, int> >::iterator it = v[el].begin(); it != v[el].end(); ++it) {
            long long newd = di + it->second;

            if(newd > sum)
                continue;

            if(dist[it->first] > newd) {

                dist[it->first] = newd;
                h.push(pair<long long, int>(dist[it->first], it->first));
            }
        }
    }
}

char pa[100];
int pp;

inline int ter() {
    int r = 0;

    while(pa[pp] >= '0' && pa[pp] <= '9')
        r = r * 10 + pa[pp++] - '0';
    ++pp;

    return r;
}

void sol() {
    int i;

    cin >> n >> m;
    for(i = 1; i <= n; ++i)
        v[i].clear();

    scanf("\n");

    for(i = 1; i <= m; ++i) {
        gets(pa); pp = 0;
        a[i] = ter();
        b[i] = ter();
        c[i] = ter();

        v[a[i]].push_back(pair<int, int>(b[i], c[i]));
        //v[b[i]].push_back(pair<int, int>(a[i], c[i]));
    }

d = 1;sum = inf;
    dij();

    int rez = 0;
    for(i = 2; i <= n; ++i) {if(dist[i] == inf)cout << "-1 ";else cout << dist[i] << " ";
    }

}

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int t;
    //cin >> t;
    //while(t--)
        sol();

    return 0;
}