#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define mmax 250005
#define inf 20000000

using namespace std;

int m, n, dist[nmax], prec[nmax];
vector < pair<int, int> > T[nmax];

void read(){
    int x, y, cost;
    ifstream f("dijkstra.in");
    f >> n >> m;
    for(int i=1; i<=m; i++){
        f >> x >> y >> cost;
        T[x].push_back(make_pair(y, cost));
    }
}

void BlF(){
    int i, j;
    for(i=1; i<=n; i++){
        for(j=0; j<T[i].size(); j++){
            if(dist[i] + T[i][j].second < dist[T[i][j].first])
                dist[T[i][j].first] = dist[i] + T[i][j].second;
        }
    }
}

int main()
{
    read();
    dist[1] = 0;
    for(int i=2; i<=n; i++)
        dist[i] = inf;
    BlF();
    ofstream g("dijkstra.out");
    for(int i=2; i<=n; i++)
        g << dist[i] << " ";
    return 0;
}