#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 50007;
const int INF = (1 << 30);

int N; int M; vector<pair <int, int> > G[NMAX];


void Dijkstra(int start) {

    bool in[NMAX]; int dist[NMAX];
    priority_queue< pair < int , int > , vector<pair<int, int> > , greater<pair <int, int> > > Q;

    memset(in, 0, sizeof(in));
    for(int i = 1 ;i <= N; ++i) dist[i] = INF;

    Q.push(make_pair(0, start));
    dist[start] = 0;

    while(!Q.empty()) {

        int nod = Q.top().second;
        int d = Q.top().first;
        Q.pop();
        in[nod] = false;
        for(unsigned i = 0 ; i < G[nod].size(); ++i) {
            if(in[G[nod][i].first] == true) continue;

            if(dist[G[nod][i].first] > d + G[nod][i].second) {
                dist[G[nod][i].first] = d + G[nod][i].second;
                Q.push(make_pair(dist[G[nod][i].first], G[nod][i].first ));
                in[G[nod][i].first] = true;
            }

        }
    }

    for(int i = 2; i <= N; ++i)
        if(dist[i] != INF)
            fout << dist[i]  <<" ";
        else fout << 0 <<" ";

}
int main() {

    fin >> N >> M;
    for(int i = 1; i <= M; ++i) {

        int A; int B; int cost;
        fin >> A >> B >> cost;
        G[A].push_back(make_pair(B, cost));
        //G[B].push_back(make_pair(A, cost));
    }
    Dijkstra(1);
    return 0;

}