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

using namespace std;

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

#define ARRAY_MAX 250000

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

vector < pair <int, int> > Node[ARRAY_MAX];

bitset <ARRAY_MAX> inQueue;

struct Compare {
    bool operator() (int X, int Y) {
        return D[X] < D[Y];
    }
};

priority_queue < int, vector <int>, Compare > Queue;

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

    for (uint16_t i = 1; i <= M; i++) {
        int X, Y, C;

        fin >> X >> Y >> C;

        Node[X].push_back(make_pair(Y, C));
    }
}

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

    D[startNode] = 0;

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

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

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

            if (D[currentNode] + Cost < D[Next]) {
                D[Next] = D[currentNode] + Cost;

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

void Write() {
    for (uint16_t i = 2; i <= N; i++)
        if (D[i] != upperBound)
            fout << D[i] << " ";
        else
            fout << "0 ";
}

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