#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const long long inf=50000*20000+1;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX=101;
int start;
int dist[NMAX];//dist[i]=distanta minima de la nodul de start la nodul i
struct elem{
    int nod;
    int cost;
    elem(int nodCrt,int c):nod(nodCrt),cost(c){};
};
vector<vector<elem>>graph;


struct alese{
    bool operator ()(int a,int b){
        return dist[a]>dist[b];
    }
};
void dijkstra(int n){
     priority_queue<int,vector<int>,alese>pq;
     
     for(int i=1;i<=n;++i){
        pq.push(i);
     }
     int crt;

     int alt;
     while (!pq.empty())
     {
        crt=pq.top();
        pq.pop();

        for(auto v:graph[crt]){
            alt=dist[crt]+v.cost;
            if(alt<dist[v.nod]){
                dist[v.nod]=alt;
                pq.push(v.nod);
            }
        }
     }
     return ;
     
}

int main(){
    int n,m;
    fin>>n>>m;
    graph.resize(n+1);
    int firstNod,secondNod,cost;
    for(int i=0;i<m;++i){
        fin>>firstNod>>secondNod>>cost;
        graph[firstNod].push_back(elem(secondNod,cost));//nu e si invers pentru ca zice ca este "graf orientat"
    }
    for(int i=0;i<=n;++i){
        dist[i]=inf;
    }
    dist[1]=0;//distanta de la nodul de start la el insusi este 0
    dijkstra(n);
    for(int i=2;i<=n;++i){
        if(dist[i]==inf){
            fout<<-1<<" ";
        }else{
            fout<<dist[i]<<" ";
        }
    }
    return 0;
}