#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define NMAX 10001
#define inf 1000001
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m,d[NMAX];

vector < pair <int,int> > mat[NMAX];

struct compara{
    bool operator()(int i,int j){
        return d[i] > d[j];
    }
};
priority_queue <int,vector<int>,compara> coada;
bool incoada[NMAX];
void citire(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x,y,cost;
        cin >> x >> y >> cost;
        mat[x].push_back(make_pair(y,cost));
    }
}
void dijkstra(int nodstart){
    for(int i = 1; i <= n; i++)
        d[i] = inf;
    d[nodstart] = 0;coada.push(nodstart);
    incoada[nodstart] = true;

    while(!coada.empty()){
        int p = coada.top();
        coada.pop();
        incoada[p] = false;
        for(size_t i = 0; i < mat[p].size(); i++){
            int vec = mat[p][i].first;
            int cst = mat[p][i].second;
            if(d[p] + cst < d[vec]){
                d[vec] = d[p] + cst;
                if(incoada[vec] == false)
                {
                    coada.push(vec);
                    incoada[vec] = true;
                }
            }
        }
    }
}
void afi(){
    for(int i = 2; i <= n; i++)
        if(d[i] != inf)
            cout << d[i] << " ";
        else
            cout << "0 ";
}
int main(){
    citire();
    dijkstra(1);
    afi();
}