#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;

int Nodes, Edges, Dist[NMAX];
bool InsideOfQueue[NMAX];
vector < pair < int, int > > Edge[NMAX];

inline static void Initialize(){
    for(int i = 1; i <= Nodes; ++i)
        Dist[i] = INF;
    return ;
}

inline void Dijkstra(){
    Initialize();
    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > Q;
    Dist[1] = 0;
    Q.push(make_pair(0, 1));
    InsideOfQueue[1] = true;
    while( ! Q.empty()){
        auto P = Q.top();
        Q.pop();
        InsideOfQueue[P.second] = false;
        if(Dist[P.second] < P.first)
            continue;
        for(auto Neighbour: Edge[P.second])
            if(Dist[Neighbour.first] > Dist[P.second] + Neighbour.second){
                Dist[Neighbour.first] = Dist[P.second] + Neighbour.second;
                if( ! InsideOfQueue[Neighbour.first]){
                    InsideOfQueue[Neighbour.first] = true;
                    Q.push(make_pair(Dist[Neighbour.first], Neighbour.first));
                }
            }
    }
}

int main(){

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> Nodes >> Edges;
    int node1, node2, cost;
    for(int i = 1; i <= Edges; ++i){
        cin >> node1 >> node2 >> cost;
        Edge[node1].push_back(make_pair(node2, cost));
    }
    Dijkstra();
    for(int i = 2; i <= Nodes; ++i)
        cout << (Dist[i] == INF ? 0 : Dist[i]) << ' ';

    return 0;
}