#include<iostream>
#include<vector>
#include<fstream>
#include<climits>
#include<queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;
int n,m;
bool vizitat[nmax];
vector<pair<int,int>> g[nmax];
vector<int> cost(nmax,INT_MAX);
queue<int> q;

void bfs(int nod){
    q.push(nod);
    while(!q.empty()){
        for(pair<int,int> vec : g[q.front()]){
            if(cost[vec.first] > cost[q.front()] + vec.second)
                cost[vec.first] = cost[q.front()] + vec.second;
            if(vizitat[vec.first] == 0){
                vizitat[vec.first] = 1;
                q.push(vec.first);
            }
        }
        q.pop();

    }
}

int main(){
    fin>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,z;
        fin>>x>>y>>z;
        g[x].push_back(make_pair(y,z));
    }
    cost[1] = 0;
    bfs(1);
    for(int i = 2; i <= n; i++)fout<<cost[i]<<" ";

}