#include <fstream>
#include <cstring>
#include <vector>
#include <list>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nmax = 50005;
const int INF = 0x3f3f3f3f;

int d[nmax];

vector<pair<int, int> >G[nmax];

//void dijkstra(/*bool &o*/){
//vector<int>coada;
//int p=0, u=0;
//coada.push_back(1);
//while(p<=u){
//    int x = coada[p];
//    for(vector<pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it){
//        int to = it->first;
//        int cost = it->second;
//        if(d[to] > d[x] + cost){
//            coada.push_back(to);
//            d[to] = d[x] + cost;
//            ++u;
//        }
//    }
//    ++p;
////    if(coada.size()>2000000){
////            o = true;
////            return;
////    }
//}
//}

void dijkstra(/*bool &o*/){
list<int>coada;
int p=0, u=0;
coada.push_back(1);
while(p<=u){
    list<int>::iterator it = coada.begin();
    int x = *it;
    for(vector<pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it){
        int to = it->first;
        int cost = it->second;
        if(d[to] > d[x] + cost){
            coada.push_back(to);
            d[to] = d[x] + cost;
            ++u;
        }
    }
    coada.erase(it);
    ++p;
}
}

int main(){

int n,m;

f>>n>>m;

for(int i=1;i<=m;++i){
    int x,y,cost;
    f>>x>>y>>cost;
    G[x].push_back(make_pair(y,cost));
}

memset(d, INF, sizeof d);

d[1] = 0;

//bool o = false;

dijkstra();
//dijkstra(o);

//if(!o){
for(int i=2;i<=n;++i)
    d[i] != INF ? g<<d[i]<<" " : g<<0<<" ";
g<<'\n';
//}
//else g<<"Ciclu negativ!"<<'\n';

return 0;
}