//
//  dijkstra.cpp
//  Algoritmul lui Dijkstra
//
//  Created by Andrei Constantinescu on 17.04.2013.
//  Copyright (c) 2013 Andrei Constantinescu. All rights reserved.
//

#include <fstream>
#include <iostream>
#define MAX 5000
using namespace std;

int n, m, a[100][100], d[100], p[100], s[100];

ifstream f("date.in");
ofstream g("dijkstra.out");

void initializare() {
    int i, j;
    f >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i != j)
                a[i][j] = MAX;
}

void citire() {
    int i, j, cost = 0;
    for (int x = 1; x <= m; x++) {
        f >> i >> j >> cost;
        a[i][j] = cost;
    }
    f.close();
}

void dijkstra(int x) {
    int i, j, min, y;
    s[x] = 1;
    for (i = 1; i <= n; i++) {
        d[i] = a[x][i];
        if (i != x && d[i] < MAX)
            p[i] = x;
    }
    for (i = 1; i <= n - 1; i++) {
        for (j = 1, min = MAX; j <= n; j++)
            if (s[j] == 0 && d[j] < min) {
                min = d[j];
                y=j;
            }
        s[y] = 1;
        for (j = 1; j <= n; j++)
            if (s[j] == 0 && d[j] > d[y] + a[y][j]) {
                d[j] = d[y] + a[y][j];
                p[j] = y;
            }
    }
}

void afisare_cost(int x) {
    for (int i = 2; i <= x; i++)
        g<<d[i]<<" ";
}

void afisare_drum(int x) {
    if (p[x] != 0)
        afisare_drum(p[x]);
    g<<x<<" ";
}

void afisare(int x) {
    for (int i = 1; i <= n; i++)
        if (i != x) {
            if (p[i] != 0) {
                //g<<"drum de la " << x <<" la " << i << ": ";
                //afisare_drum(i);
                cout<<d[i]<<" ";
                afisare_cost(i);
                //g<<"\n";
            }
            else g<<"NU ";
        }
}
int main() {
    initializare();
    citire();
    dijkstra(1);
    afisare(1);
    g.close();
}