#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define Nmax 50010
#define inf 199999

using namespace std;

int dis[Nmax], par[Nmax];
int nvarfuri, nmuchii, start = 1;
vector < pair < int, int > > graf[Nmax];

class ComparaVf{
public:
    bool operator()(int x, int y){
        return dis[x] < dis[y];
    }
};

priority_queue<int, vector<int>, ComparaVf> H;

void citire();
void initializare();
void relaxare(int u,int v,int w);
void dijkstra();
void afisare();

int main(){

    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire(){
    
    int x, y, c;
    ifstream f("dijkstra.in");
    f >> nvarfuri >> nmuchii;

    for(int i = 1; i <= nmuchii; i++){
        f >> x >> y >> c;
        graf[x].push_back(make_pair(y, c));
    }
}

void initializare(){
    
    for(int i = 1; i <= nvarfuri; i++){
        dis[i] = inf;
        par[i] = -1;
    }
    dis[start] = 0;
    par[start] = 0;
}

void relaxare(int u, int v, int w){
    if(dis[u] > dis[v] + w){
       dis[u] = dis[v] + w;
       par[u] = v;
       H.push(u);
    }
    
}

void dijkstra(){
    initializare();
    int vfMin;
    H.push(start);
    while(!H.empty()){
        vfMin = H.top();
        H.pop();
        for(int i = 0; i < graf[vfMin].size(); i++)
            relaxare(graf[vfMin][i].first, vfMin, graf[vfMin][i].second);
                
    }
}

void afisare(){
   
   ofstream g("dijkstra.out");
   for(int i = 2; i <= nvarfuri; i++)
        if(dis[i] == inf)
            g << 0 << " ";
        else
            g << dis[i] << " ";
    
}