#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
#include <string.h>
#define NMax 50001
#define INF 9999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,dist[NMax];
vector <pair<int,int> >graf[NMax];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Queue;
void read(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int from,to,cost;
        fin>>from>>to>>cost;
        graf[from].push_back(make_pair(to,cost));}
}
void dijkstra(int source){
    memset(dist,INF,sizeof(dist));
    dist[source]=0;
    Queue.push(make_pair(0,source));
    while(!Queue.empty()){
        int nod=Queue.top().second;
        int d=Queue.top().first;
        Queue.pop();
        if(dist[nod]!=d)
            continue;
        for(int i=0;i<graf[nod].size();i++){
            int to=graf[nod][i].first;
            int cost=graf[nod][i].second;
            if(dist[to]>dist[nod]+cost){
                dist[to]=dist[nod]+cost;
                Queue.push(make_pair(dist[to],to));
            }
        }
    }
}
void afis(){
    for(int i=0;i<=n;i++)
        if(dist[i]<INF && dist[i]!=0)
            fout<<dist[i]<<" ";}

int main(){
    read();
    dijkstra(1);
    afis();
    return 0;}