#include <bits/stdc++.h>
#define DIM 250000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, a, b, c, cost_fiu, fiu, cost_nod, nod;
int drum[DIM];
int i, j;
pair <int, int> temp;
vector <pair <int, int> > G[DIM];
set <pair <int, int> > s;

int main(){
    fin>>n>>m;
    for(i=1; i<=n; i++){
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b, c));
    }
    for(i=2; i<=n; i++)
        drum[i]=DIM;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        temp=*s.begin();
        nod=temp.second;
        cost_nod=temp.first;
        s.erase(s.begin());
        for(auto k:G[nod]){
            fiu=k.first;
            cost_fiu=k.second;
            if(drum[fiu]>drum[nod]+cost_fiu){
                s.erase(make_pair(drum[fiu], fiu));
                drum[fiu]=drum[nod]+cost_fiu;
                s.insert(make_pair(drum[fiu], fiu));
            }
        }
    }
    for(i=2; i<=n; i++){
        if(drum[i]>=DIM)
            drum[i]=0;
        fout<<drum[i]<<" ";
    }
}