#include <vector>
#include <queue>
#include <fstream>
#include <cstdio>
#include <climits>
using namespace std;
FILE *f = fopen("dijkstra.in", "rt");
ofstream out("dijkstra.out");

//const int INF = 0x3f3f3f3f;
vector <pair<int, int> > G[50002];
int n, m;
int distMin[50002];

void read(){
    fscanf(f, "%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        int a, b, c;
        fscanf(f, "%d%d%d", &a, &b, &c);
        G[a].push_back(make_pair(b,c));
    }
}
void dijkstra(){
    //bool viz[50002];
    queue <int> q;
    //memset(distMin, INF, sizeof(distMin));
    //memset(viz, false, sizeof(viz));
    for(int i=1;i<=n;i++)distMin[i]=INT_MAX;
    //for(int i=1;i<=n;i++)viz[i]=false;
    distMin[1]=0;
    //viz[1]=true;
    q.push(1);

    while(!q.empty()){
        int nod = q.front();
        q.pop();
        //viz[nod] = false;

        for(vector<pair <int, int> >::iterator it = G[nod].begin();it!=G[nod].end();++it ){
            if(distMin[nod] + it->second < distMin[it->first]){
                distMin[it->first] = distMin[nod] + it->second;
                q.push(it->first);
            }
           /* if(!viz[it->first]){
                q.push(it->first);
                viz[it->first] = true;
            }*/
        }
    }

}
void afisare(){
    for(int i=2;i<=n;i++){
        if(distMin[i]==INT_MAX)
            out<< '0' <<' ';
        else out<<distMin[i]<< ' ';
    }

}

int main()
{
    read();
    dijkstra();
    afisare();
    return 0;
}