///DIJKSTRA HOME 04.01
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>

using namespace std;

const int MAXINT = numeric_limits<int>::max();

struct Edge {
    int to, cost;
    Edge(int a, int b) {to = a; cost = b;}
    Edge() {to = 0; cost = 0;}
};

struct Compare {bool operator () (Edge& a, Edge& b) {return a.cost > b.cost;}};

void dijkstra(vector<list<Edge> >& adjList, vector<int>& minCost) {
    priority_queue<Edge, vector<Edge>, Compare> pq;
    pq.push(Edge(0, 0));

    minCost.assign(adjList.size(), MAXINT);
    minCost[0] = 0;

    Edge current;
    list<Edge>::iterator it;
    while(!pq.empty()) {
        current = pq.top();
        pq.pop();

        if(current.cost > minCost[current.to])
            continue;

        for(it = adjList[current.to].begin(); it != adjList[current.to].end(); it++)
            if(it -> cost + minCost[current.to] < minCost[it -> to]) {
                minCost[it -> to] = it -> cost + minCost[current.to];
                pq.push(*it);
            }
    }
}

int main() {
    ifstream inStr("dijkstra.in");
    ofstream outStr("dijkstra.out");

    int N, M;
    inStr >> N >> M;

    vector<list<Edge> > adjList(N);

    int from, to, cost;
    for(int i=0; i<M; i++) {
        inStr >> from >> to >> cost;
        adjList[--from].push_back(Edge(--to, cost));
    }

    vector<int> minCost;
    dijkstra(adjList, minCost);

    for(int i=1; i<N; i++)
        if(minCost[i] == MAXINT)
            outStr << 0 << ' ';
        else
            outStr << minCost[i] << ' ';
    outStr << '\n';

    return 0;
}