#include    <fstream>
#include    <vector>
#include    <queue>
#include    <bitset>

using namespace std;

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

#define ARRAY_MAX 250005

int N, M;
int Dist[ARRAY_MAX];
const int upperBound = 1 << 30;

bitset < ARRAY_MAX > inQueue;
vector < pair < int, int > > Node[ARRAY_MAX];
priority_queue < int, vector < int > > Queue;

void Read() {
    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        int A, B, C;
        fin >> A >> B >> C;

        Node[A].push_back(make_pair(B, C));
    }
}

void Dijkstra(int startNode) {
    for (int i = 1; i <= N; i++)
        Dist[i] = upperBound;

    Dist[startNode] = 0;
    Queue.push(startNode);
    inQueue[startNode] = true;

    while (!Queue.empty()) {
        int currentNode = Queue.top();
        Queue.pop();
        inQueue[currentNode] = false;

        for (int i = 0; i < Node[currentNode].size(); i++) {
            int Next = Node[currentNode][i].first;
            int Cost = Node[currentNode][i].second;

            if (Dist[Next] > Dist[currentNode] + Cost) {
                Dist[Next] = Dist[currentNode] + Cost;

                if (!inQueue[Next]) {
                    Queue.push(Next);
                    inQueue[Next] = true;
                }
            }
        }
    }
}

void Write() {
    for (int i = 2; i <= N; i++)
        if (Dist[i] != upperBound)
            fout << Dist[i] << " ";

        else
            fout << "0 ";
}

int main() {
    Read();
    Dijkstra(1);
    Write();
}