#include <bits/stdc++.h>
#define MAXN 100000

int n,min[MAXN+1];

struct Edge{
    int to;
    int cost;
};

bool operator < ( const Edge & a, const Edge & b){
    return a.cost>b.cost;
}

std::vector < Edge > edges[MAXN+1];
std::priority_queue < Edge > q;

void solve(){
    Edge aux,node;
    for(auto x : edges[1])
        q.push(x);
    while(!q.empty()){
        node=q.top();
        if(node.cost<min[node.to]){
            min[node.to]=node.cost;
            for(auto x : edges[node.to]){
                aux.cost=node.cost+x.cost;
                aux.to=x.to;
                q.push(aux);
            }
        }
        q.pop();
    }
    FILE *fout=fopen("dijkstra.out", "w");
    for(int i=2; i<=n; i++)
        fprintf(fout, "%d ", min[i]);
}

int main()
{
    FILE *fin;
    int m,i,x,y,c;
    fin=fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &c);
        edges[x].push_back({y, c});
    }
    for(i=1; i<=n; i++)
        min[i]=1000000001;
    min[1]=0;
    solve();
    return 0;
}