#include <fstream>
#include <queue>
#include <vector>
#define inf 500000000
using namespace std;

int n,m,s=1,c,xs,ys;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{
    int val,nodv;

}temp;

vector< vector <nod> > graf;
vector < int > cost;
queue < int > q;

void citesc(){

f >> n >> m;
graf.resize(n+1);

    for(int i=1;i<=m;i++){
        f >> xs >> ys >> c;
        temp.val = c;
        temp.nodv = ys;
        graf[xs].push_back(temp);
    }
}

void Dijkstra(){

int first = s;
cost.resize(n+1,inf);
q.push(first);
cost[s] = 0;

    while(!q.empty()){
    for(vector<nod>::iterator it = graf[first].begin();it!=graf[first].end();++it){
        if(cost[it->nodv] > cost[first] + it->val){
            q.push(it->nodv);
            cost[it->nodv] = cost[first] + it->val;
        }
}
    q.pop();
    first = q.front();
}
 }


int main(){

    citesc();
    Dijkstra();

for(int i=1;i<=n;i++){
    if(i == s)
        continue;
    if(cost[i] == inf)
    g << " 0 ";
    else g << cost[i] << " ";
}
    f.close();
    g.close();
return 0;
}