#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]; bool viz[NMAX];


void Dijkstra(int start) {

    int dist[NMAX];
    queue< pair < int , int > > Q;

    for(int i = 1 ;i <= N; ++i) dist[i] = INF;
    memset(viz, 0, sizeof(viz));
    viz[start] = true;
    Q.push(make_pair(0, start));
    dist[start] = 0;

    while(!Q.empty()) {

        int nod = Q.front().second;
        int d = Q.front().first;
        Q.pop();
        viz[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;
                if(viz[G[nod][i].first]) continue;
                Q.push(make_pair(dist[G[nod][i].first], G[nod][i].first ));
                viz[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;

}