#include <iostream>

#include <fstream>

#include <vector>

#include <queue>

#include <limits.h>

#define NLIM 50001



using namespace std;

ifstream f("dijkstra.in");

ofstream g("dijkstra.out");



vector< pair<int, int> > Muchii[NLIM];

bool mark[NLIM];

int dis[NLIM];

struct cmpDis {

    bool operator()(int a, int b) {

        return dis[a] > dis[b];

    }

};



priority_queue<int, vector<int>, cmpDis> Coada;



void citire(int &n, int &m) {

    f >> n >> m;

    for(int i=1; i<=n; i++) dis[i] = INT_MAX;

    for(int i=1; i<=m; i++) {

        int s, d, c;

        f >> s >> d >> c;

        Muchii[s].push_back(make_pair(d, c));

    }

}



void Dijkstra(int start) {

    dis[start] = 0;



    Coada.push(start);

    mark[start] = 1;



    while(!Coada.empty()) {

        int nod = Coada.top();

        Coada.pop();

        mark[start] = 0;



        for(int i=0; i<Muchii[nod].size(); i++) {

            int vecin = Muchii[nod][i].first;

            int cost = Muchii[nod][i].second;



            if(dis[nod]+cost < dis[vecin]) {

                dis[vecin] = dis[nod]+cost;

                if(!mark[vecin]) {

                    Coada.push(vecin);

                    mark[vecin] = 1;

                }

            }

        }

    }

}



int main() {

    int n, m;



    citire(n, m);

    Dijkstra(1);



    for(int i=2; i<=n; i++)

        if(dis[i] != INT_MAX)

            g << dis[i] << ' ';

        else g << "0 ";



    return 0;

}