#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define NMAX 50001
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(int m){
    for(auto u:v[m]){
        q.push(u);
    }
    while(!q.empty()){
        elem x=q.top();
        q.pop();
        if(x.cost<dist_min[x.catre]){
            ///daca costul cu care am ajuns la nodul curent
            ///este mai mic decat costul curent al nodului
            ///il punem, si punem si vecinii lui
            dist_min[x.catre]=x.cost;
            for(auto u:v[x.catre]){
                elem nr;
                nr.cost=x.cost+u.cost;
            ///punem cu costul curent
                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;
        v[x].push_back({y,z});
    }
    for(int i=2;i<=n;i++){
        dist_min[i]=100001;
    }
    dijkstra(1);
    return 0;
}