#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
const int NMAX = 50001;
priority_queue <pair<int, int> > pq;
bool visited[NMAX];
int distante[NMAX];
vector <pair<int, int> > G[NMAX];
int main()
{
    FILE *fin, *fout;
    int n,m,i,nod1,nod2,w,nod,p;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i = 1; i <= m; i++){
        fscanf(fin,"%d %d %d",&nod1,&nod2,&w);
        G[nod1].push_back(make_pair(nod2,w));
    }
    distante[1] = 0;
    for(i = 2; i <= n; i++)
        distante[i] = INF, visited[i] = false;
    pq.push(make_pair(-distante[0],1));
    while(!pq.empty()){
        if(!pq.empty() && visited[pq.top().second] == true){
            pq.pop();
            continue;
        }
        nod = pq.top().second;
        visited[nod] = true;
        pq.pop();
        for(p = 0; p < G[nod].size(); p++)
            if(distante[G[nod][p].first] > distante[nod] + G[nod][p].second){
                distante[G[nod][p].first] = distante[nod] + G[nod][p].second;
                pq.push(make_pair(-distante[G[nod][p].first],G[nod][p].first));
            }
    }
    for(i = 2; i <= n; i++)
        if(distante[i] == INF)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",distante[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}