#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <queue>
//#include <pair>
#define NMAX 50002
#define INF 100000
using namespace std;
//                      BELMAN FORD
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair<int,int> > muchii[NMAX];//first = muchie second = cost
int cost[NMAX]={INF};

void BelmanFord(int start,int n){
    queue<int> coada;
    coada.push(start);
    for(int i=1;i<=n;i++)
        cost[i]=INF;
    cost[start]=0;
    while(!coada.empty()){
        int el = coada.front();
        coada.pop();
        for(vector< pair <int,int> >::iterator it=muchii[el].begin();it!=muchii[el].end();it++){
            if(cost[it->first] > cost[el] + it->second ){
                cost[it->first] = cost[el] + it->second;
                coada.push(it->first);
            }
        }
    }
}

void afisare(int start,int n){
    for(int i=1;i<=n;i++)
        if(i!=start){
            if(cost[i]==INF)
                g << 0 << " ";
            else
                g << cost[i] << " ";
        }
}

int main()
{
    int n,m,a,b,c;
    f >> n >> m;
    for(int i=0;i<m;i++){
        f >> a >> b >> c;
        muchii[a].push_back(make_pair(b,c));
    }
    BelmanFord(1,n);
    afisare(1,n);
    return 0;
}