#include <fstream>
#include <vector>
#include <set>
#include <queue>
#define MAXN 50005
#define INFINIT 2000000005
#define pb push_back
#define mp make_pair
using namespace std;

typedef pair <int, int> edge;
typedef vector <edge> graf;
typedef priority_queue <edge> Heap;

graf G[MAXN + 1];
Heap H;
int D[MAXN + 1];

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

    int n, m;
    fin >> n >> m;
    for (int i = 0 ; i < m ; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].pb(mp(c, b));
    }
    for (int i = 1 ; i <= n ; ++i)
        D[i] = INFINIT;

    D[1] = 0;
    H.push(mp(0, 1));
    while (!H.empty()) {
        edge E = H.top();
        H.pop();

        int node = E.second;
        for (graf :: iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
            if (D[node] + it -> first < D[it -> second]) {
                D[it -> second] = D[node] + it -> first;
                H.push(mp(-D[it -> second], it -> second));
            }
        }
    }

    for (int i = 2 ; i <= n ; ++i)
        fout << D[i] << " ";

    return 0;
}