#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
#include <climits>
using namespace std;

struct Muchie{
    int s;
    int d;
    int cost;
};

vector<Muchie> muchii;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int dist[50001];
bool vis[50001];



//cu lista de adiacenta
int main(){


    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n;
    cin>>n;
    int m;
    cin>>m;

    for(int i=1; i<=n; i++){
        dist[i]=INT_MAX;
    }

    dist[1]=0;

    pq.push({dist[1], 1});

    for(int i=0; i<m; i++){
        int x,y,c;
        cin>>x>>y>>c;
        muchii.push_back(Muchie{x,y,c});
    }

    while(!pq.empty()){
        int nod=pq.top().second;

        pq.pop();

        if(vis[nod]==1){
            continue;
        }

        vis[nod]=1;
        for(int i=0; i<muchii.size(); i++){
            if(muchii[i].s == nod){
                int vecin = muchii[i].d;
                int cost=muchii[i].cost;
                if(dist[vecin]>dist[nod]+cost){
                    dist[vecin]=dist[nod]+cost;
                    pq.push({dist[vecin], vecin});
                }
            }
        }
    }

    for(int i=2; i<=n; i++){
        cout<<dist[i]<<" ";
    }

    return 0;
}