#include <bits/stdc++.h>
using namespace std;

// Uncomment the next lines for file I/O

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


#define fast ios::sync_with_stdio(false); cin.tie(nullptr)
#define ll long long
//celelalte noduri vor avea distanta infinita initial
#define INF 2e9

// Structura pentru muchii

struct edge {
    int nod;
    int cost;
    bool operator<(const edge& x) const {
        return cost > x.cost; // For min-heap
    }
};

// Graf reprezentat ca lista de adiacență
vector <pair<int,int>> graf[50005];
// Coada de priorități pentru Dijkstra
priority_queue <edge> pq;
// Vector pentru distanțe
int dist[50005];

int main() {
    fast;

    int n,m;
    fin >> n >> m;
    dist[1] = 0;
    for(int i=2;i<=n;i++) dist[i] = INF;

    for(int i=1;i<=m;i++){
        int x,y,cost;
        fin >> x >> y >> cost;
        // Process the input as needed
        graf[x].push_back({y,cost});
        //graf[y].push_back({x,cost});
    }
    // initializare coada de priorități cu nodul sursă
    pq.push({1,0});
    // Algoritmul Dijkstra
    while(!pq.empty()){
        edge curr = pq.top();
        pq.pop();
        int nod = curr.nod;
        // Relaxarea muchiilor
        //parcurgem toti vecinii nodului curent
        //si actualizam distantele
        //daca gasim o distanta mai mica pentru un vecin
        //il adaugam in coada de prioritati
        //pentru a fi procesat ulterior
        for(int i=0;i<graf[nod].size();i++){
            int vecin = graf[nod][i].first;
            int cost = graf[nod][i].second;
            if(dist[nod] + cost < dist[vecin]){
                dist[vecin] = dist[nod] + cost;
                pq.push({vecin, dist[vecin]});
            }
           /*if(dist[nod]+graf[nod][i].second < dist[graf[nod][i].first]){
                dist[graf[nod][i].first] = dist[nod] + graf[nod][i].second;
                pq.push({graf[nod][i].first, dist[graf[nod][i].first]});
           }*/
        }
    }
    // Afisam distantele de la nodul 1 la toate celelalte noduri
    for(int i=2;i<=n;i++){
        if(dist[i] == INF){
            fout << "0 ";
        } else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}