#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>

using namespace std;

vector <pair <int,int> > g[50001];
priority_queue <pair <int,int>, vector < pair <int,int> > ,greater <pair <int,int> > > heap;
int dist[50001];
int n;

void dij(int start){
    int son, nod, cost, distson;
    for(int i=1;i<=n;i++)
        dist[i]=1000000000;
    dist[start]=0;
    heap.push({0,start});
    while(heap.empty()==0){
        nod=heap.top().second;
        cost=heap.top().first;
        heap.pop();
        if(cost<=dist[nod]){
            for(int i=0;i<g[nod].size();i++){
                son=g[nod][i].first;
                distson=g[nod][i].second;
                if(dist[son]>cost+distson){
                    dist[son]=cost+distson;
                    heap.push({dist[son],son});
                }
            }
        }
    }
}

int main()
{
    FILE *fin, *fout;
    int m,i,j,cost,a,b;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(i=0;i<m;i++){
        fscanf(fin,"%d%d%d",&a,&b,&cost);
        g[a].push_back(make_pair(b,cost));
    }
    dij(1);
    for(i=2;i<=n;i++){
        if(dist[i]!=1000000000)
            fprintf(fout,"%d ",dist[i]);
        else
            fprintf(fout,"0 ");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}