#include <fstream>
#include <vector>
#include <set>

#define DIM 50015
#define INF DIM*1005

using namespace std;

vector < pair<int, int> > L[DIM];
set < pair<int, int> > s;

int V[DIM], D[DIM], i, x, y, c, n, m, k;

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

int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
    }
    for (i=1;i<=n;i++) {
        D[i] = INF;
    }
    D[1] = 0;
    s.insert(make_pair(0,1));
    while (!s.empty()) {
        k = s.begin()->second;
        s.erase( s.begin() );
        for (i=0;i<L[k].size();i++)
            if (D[ L[k][i].first ] > D[k] + L[k][i].second) {
                s.erase (  make_pair(D[ L[k][i].first ], L[k][i].first) );
                D[ L[k][i].first ] = D[k] + L[k][i].second;
                s.insert (  make_pair(D[ L[k][i].first ], L[k][i].first) );
            }
    }

    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";

}