#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

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

const int MAX_SIZE = 50005;
const int MAX_SUM = 20000000;

vector<int> graph[MAX_SIZE];
int costs[MAX_SIZE][MAX_SIZE];
int minSum = MAX_SUM, currentSum = 0;
int prevSum = 0, curSum = 0;

void findMinimumCost(int endPeak, int currentPeak, int prevPeak) {
    if (graph[currentPeak].size() == 0 || currentPeak == endPeak) {
        if (currentPeak == endPeak && currentSum < minSum) {
            minSum = currentSum;
        }
        //cout << "in return:" << prevPeak << " " << currentPeak << " " << currentSum << "\n";
        prevSum = prevPeak;
        curSum = currentPeak;
        return;
    } // trebuie sa vad cum schimb valoarea lui currentSum cand ma intorc din recursivitate
    for (int i = 0; i < graph[currentPeak].size(); ++i) {
        currentSum += costs[currentPeak][graph[currentPeak][i]];
        //cout << currentPeak << " " << graph[currentPeak][i] << " " << currentSum << "\n";
        findMinimumCost(endPeak, graph[currentPeak][i], currentPeak);
        //cout << "ne intoarcem: ";
        currentSum -= costs[prevSum][curSum];
        prevSum = prevPeak;
        curSum = currentPeak;
        //if (prevPeak == 0) {
          //  currentSum = 0;
        //}
        //cout << prevPeak << " " << currentPeak << " " << currentSum << "\n";
        //cout << "\n";
    }
}

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(end);
        costs[start][end] = cost;
    }
    for (int destination = 2; destination <= peaks; ++destination) {
        minSum = MAX_SUM;
        findMinimumCost(destination, 1, 0);
        if (minSum == MAX_SUM) {
            minSum = 0;
        }
        fout << minSum << " ";
    }
    return 0;
}
 /*
  
  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.
  
  
  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
  
  
  
  */