#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
const  int inf = 1<<31-1;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<vector<pair<int, int>>> adj_list;
//vector<int> viz;
vector<int> dist;
set<pair<int,int>> pq;

int n, m;

void dijkstra(int nod_start, int n) {
   // viz.assign(n+1, 0);
    dist.assign(n+1, inf);
    dist[nod_start] = 0;
    pq.insert({dist[nod_start], nod_start});
    while (!pq.empty()){
            auto p=pq.begin();
            pair<int, int> nod_curent = *p;
            cout<<nod_curent.second;
            pq.erase(p);
        //if (viz[nod_curent.second])
            //continue;
       // if (dist[nod_curent.second]< nod_curent.first)//nod_curent este extras cu o etichtea mai mare
          //  continue;
      //  viz[nod_curent.second] = 1;
        for (auto &v : adj_list[nod_curent.second]){
         //   if (!viz[v.first]){
                if (dist[v.first] > dist[nod_curent.second] + v.second) {
                    pq.erase({dist[v.first], v.first});
                    dist[v.first] = dist[nod_curent.second] + v.second;
                    pq.insert({dist[v.first], v.first});
                }
          //  }
        }
    }
    for (int i = 2; i<=n; i++) {
        if (dist[i] == inf)
        {
            fout<<0<<" ";
            continue;
        }
        fout<<dist[i]<<" ";
    }
}

int main() {
 fin>>n>>m;
 adj_list.assign(n+1, {});


 for (int i =0; i< m; i++) {
    int x,y,c;
    fin>>x>>y>>c;
    adj_list[x].push_back({y, c});
 }
 dijkstra(1, n);




return 0;}