#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <queue>
using namespace std;

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

const int MAX_SIZE = 50005;
const int MAX_SUM = 1000000001;

vector<pair<int, int>> graph[MAX_SIZE];

int main() {
    int peaks, arches;
    fin >> peaks >> arches;
    for (int i = 1; i <= arches; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        graph[start].push_back(make_pair(end, cost));
    }
    int distances[MAX_SIZE];
    distances[1] = 0;
    for (int i = 2; i <= peaks; ++i) {
        distances[i] = MAX_SUM;
    }
    set<pair<int, int>> positions;
    positions.insert(make_pair(1, 0)); // punct / cost
    while (!positions.empty()) {
        int cost = positions.begin()->second;
        int currentPeak = positions.begin()->first;
        positions.erase(positions.begin());
        for (pair<int, int> p : graph[currentPeak]) {
            int nextPoint = p.first;
            int nextCost = p.second;
            if (distances[nextPoint] > cost + nextCost) {
                if (distances[nextPoint] != MAX_SUM) {
                    positions.erase(positions.find(make_pair(nextPoint, distances[nextPoint])));
                }
                distances[nextPoint] = cost + nextCost;
                positions.insert(make_pair(nextPoint, distances[nextPoint]));
            }
         }
        
    }
    for (int i = 2; i <= peaks; ++i) {
        if (distances[i] == MAX_SUM) {
            distances[i] = 0;
        }
        fout << distances[i] << " ";
    }

    
}

/*
  
  1 ≤ N ≤ 50 000
  1 ≤ M ≤ 250 000
  Lungimile arcelor sunt numere naturale cel mult egale cu 20 000.
  Pot exista arce de lungime 0
  Nu exista un arc de la un nod la acelasi nod.
  Daca nu exista drum de la nodul 1 la un nod i, se considera ca lungimea minima este 0.
  Arcele date in fisierul de intrare nu se repeta.
  
  50000 7
  1 2 1
  2 3 2
  3 4 3
  4 5 1
  1 5 700
  2 5 100
  3 5 30 -> 1 3 5 7 + multe 0-uri
  
  5 7
  1 2 1
  2 3 2
  3 4 3
  4 5 1
  1 5 700
  2 5 100
  3 5 30 -> 1 3 6 7
  
  5 3
  1 5 2
  1 4 5
  5 4 1 -> 0 0 3 2
  
  5 3
  1 5 2
  1 4 3
  5 4 1 -> 0 0 3 2
  
  
  3 1
  1 2 1 -> 1 0
  
  4 4
  1 2 1
  1 3 2
  3 4 1
  2 4 1 -> 1 2 2
  
  
  5 6
  1 2 1
  1 4 2
  4 3 4
  2 3 2
  4 5 3
  3 5 6 -> 1 3 2 5
  
  
  
  */