#include<fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX = 50005;
const int INF = (1 << 30);

struct compare{
    bool operator()(const pair<int,int>& a,const pair<int,int>& b){
        return a.first < b.first;
    }
};

vector<pair<int,int> > G[NMAX];
priority_queue<pair<int,int> , vector<pair<int,int> > , compare > heap;
int N,M,sol[NMAX];

int main()
{

    in>>N>>M;
    int x,y,c;
    for(int i = 1 ; i <= M ; ++i){

        in>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    in.close();
    heap.push(make_pair(0,1));
    for(int i = 2 ; i <= N ; ++i)
        sol[i] = INF;
    while(!heap.empty()){

        pair<int,int> act = heap.top();
        int nod = act.second;
        int cost = act.first;
        heap.pop();
        for(vector<pair<int,int> >::iterator it = G[nod].begin() ; it != G[nod].end() ; ++it)
            if(cost + (*it).second < sol[(*it).first]){

                sol[(*it).first] = cost + (*it).second;
                heap.push(make_pair(sol[(*it).first],(*it).first));
            }
    }
    for(int i = 2 ; i <= N ; ++i)
        if(sol[i] == INF)
            out<<"0 ";
        else out<<sol[i]<<" ";
    in.close();
    out.close();
    return 0;
}