#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct elem{
int catre,cost;
};

int n,m,x,y,z;
vector<elem> v[100001];
int dist_min[100001];

bool operator <(elem a, elem b){
    return a.cost>b.cost;
}

priority_queue<elem> q;

void dijkstra(){
    for(auto u:v[1]){
        q.push(u);
    }
    while(!q.empty()){
        elem x=q.top();
        q.pop();
        if(x.cost<dist_min[x.catre]){
            dist_min[x.catre]=x.cost;
            for(auto u:v[x.catre]){
                elem nr;
                nr.cost=x.cost+u.cost;
                nr.catre=u.catre;
                q.push(nr);
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(dist_min[i]!=100001){
            fout<<dist_min[i];
        }
        else{
            fout<<0;
        }
        fout<<" ";
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>z;
        elem nr;
        nr.catre=y;
        nr.cost=z;
        v[x].push_back(nr);
    }
    for(int i=2;i<=n;i++){
        dist_min[i]=100001;
    }

    dijkstra();


    return 0;
}