/*
ID: gabriel100
LANG: C++
TASK:
*/
#include <cstdio>
#include <algorithm>
//#include <time.h>
#include <queue>
#include <cmath>
#include <stack>
#include <fstream>
#include <bitset>
#include <set>
#include <map>
#include <ctime>
#include <list>

#define nl '\n'
#define F first
#define S second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define eb(x) emplace_back(x)
#define ull unsigned long long
#define ll long long
#define ProblemName "dijkstra"
#define LocalName "data"
#ifdef INFOARENA
#define Filename ProblemName
#else
#define Filename LocalName
#endif
#define Input Filename".in"
#define Output Filename".out"
using namespace std;
ifstream cin(Input);
ofstream cout(Output);

template<class a, class type>
void print(a v, type t) {
    for_each(all(v), [](type x) { cout << x << ' '; });
    cout << nl;
}
#define N 50000

struct dij {
    int dist = 1000000000;
    int id;
};
struct nod {
    int dist = 1000000000;
    list<dij> lista;
};

int n, m, x, y;
nod v[N + 2];

inline void add(const int &ind, const int &val, const int &cost) {
    dij temp;
    temp.dist = cost;
    temp.id = val;
    v[ind].lista.push_back(temp);
   // if (ind == 1)
   //     v[val].dist = cost;
}

bitset<N + 3> viz;

inline void dijsktra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;
    q.push({v[start].dist, start});
    int i;
    while (!q.empty()) {
        i = q.top().S;
        q.pop();
        if (!viz[i])
            for (auto it = v[i].lista.begin(); it != v[i].lista.end(); ++it) {

                if (v[it->id].dist > v[i].dist + it->dist) {
                    v[it->id].dist = v[it->id].dist = v[i].dist + it->dist;
                    q.push({v[it->id].dist, it->id});
                }

            }
        viz[i] = 1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    clock_t tStart = clock();
    v[1].dist = 0;
    cin >> n >> m;
    int cost;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y >> cost;
        add(x, y, cost);
    }
    dijsktra(1);
    for (int i = 2; i <= n; ++i) {
        if (v[i].dist > 999999) {
            cout << "0 ";
        } else {
            cout << v[i].dist << ' ';
        }
    }
    cout.close();
    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}