#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int picked[50001];
int distanta[50001];
int tati[50001];
#define maxim 20001
 int m_adiacenta[5000][5000];

int main() {
    int N, M, A, B, C;
    fin >> N>>M;
    for (int i = 1; i <= M; i++) {
        fin >> A >> B>>C;
        m_adiacenta[A][B] = C;
    }
    for (int i = 1; i <= N; i++) {
        if (i == 1)
            distanta[i] = 0;
        else
            distanta[i] = maxim;
    }
    int nr = 0;
    int poz;
    while (nr != N) {
        int min = maxim;
        for (int i = 1; i <= N; i++) {
            if (distanta[i] < min && picked[i] == 0) {
                min = distanta[i];
                poz = i;
            }
        }
        picked[poz] = 1;
        nr++;

        for (int j = 1; j <= N; j++) {
            if ((m_adiacenta[poz][j] != 0)&& (picked[j] == 0)) {
                if (distanta[j] > (distanta[poz] + m_adiacenta[poz][j])) {
                    distanta[j] = distanta[poz] + m_adiacenta[poz][j];
                }
            }

        }
    }
    for (int i = 2; i <= N; i++)
        fout << distanta[i] << " ";
    
        return 0;
}