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

using namespace std;

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

#define ARRAY_MAX 50005

int N, M;
int Dist[ARRAY_MAX];
bool inQueue[ARRAY_MAX];
const int upperBound = (1 << 30);

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

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

    while (M--) {
        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;

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

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

        for (auto it : Node[currentNode]) {
            int Next = it.first;
            int Cost = it.second;

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

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

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

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    Read();
    Dijkstra(1);
    Write();
}