#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMax = 50005;
const int INF = 1000000005;
vector <pair <int, int> > G[NMax];
int Dist[NMax];
bool Used[NMax];
int N, M;
priority_queue <pair<int,int>, vector <pair <int, int> >, greater <pair<int, int> > > Q;
void Read(){
    f >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
}
int findMin(){
    while(Used[Q.top().second])
        Q.pop();
    int res = Q.top().second;
    Q.pop();
    return res;
}
void Dijkstra(int source){
    for(int i = 1; i <= N; i++)
        Dist[i] = INF;
    Dist[source] = 0;
    for(int i = 1; i <= N; i++){
        Q.push(make_pair(Dist[i], i));
    }
    for(int step = 1; step <= N; step++){
        int minNode = findMin();
        Used[minNode] = true;
        for(int i = 0; i < G[minNode].size(); i++){
            int neighb = G[minNode][i].first, cost = G[minNode][i].second;
            if(Dist[neighb] > Dist[minNode] + cost && !Used[neighb]){
                Dist[neighb] = Dist[minNode] + cost;
                Q.push(make_pair(Dist[neighb], neighb));
            }
        }
    }
    for(int i = 2; i <= N; i++){
        if(Dist[i] == INF)
            Dist[i] = 0;
        g << Dist[i] << " ";

    }

    g << "\n";
}
int main()
{
    Read();
    Dijkstra(1);
    /*Q.push(3);
    Q.push(2);
    Q.push(100);
    cout << Q.top() << "\n";
    Q.pop();
    cout << Q.top();*/
    return 0;
}