#include<iostream>
#include<fstream>
#include<list>
#include<queue>
#include<vector>
#include<climits>
#define iPair pair<int, int>
using namespace std;
ifstream f("dijkstra.in");
ofstream o("dijkstra.out");

class Graph{

int vf;
list<iPair>*Adj;

public:Graph(int vf){
this->vf=vf;
Adj=new list<iPair>[vf];
}

public:void addEdge(int x, int y, int weight){
Adj[x].push_back(make_pair(y, weight));
}

public:void dij(int s){

list<iPair>::iterator i;

vector<int> dist(this->vf, INT_MAX);
vector<bool> inC(this->vf, false);
priority_queue<iPair, vector<iPair>, greater<iPair> >q;
q.push(make_pair(0,s));
dist[s]=0;

while(!q.empty()){
s=q.top().second;
q.pop();
inC[s]=false;
for(i=Adj[s].begin();i!=Adj[s].end();i++){
if(dist[(*i).first]>dist[s]+(*i).second){
dist[(*i).first]=dist[s]+(*i).second;
if(!inC[(*i).first]){
q.push(make_pair(dist[(*i).first], (*i).first));
inC[(*i).first]=true;
}
}
}
}

for(int i=1;i<this->vf;i++){
if(dist[i]==INT_MAX) o<<0<<" ";
else o<<dist[i]<<" ";
}

}
};

int main(){
int vf, m, x, y, w;
f>>vf>>m;
Graph g(vf);
while(f>>x){
f>>y>>w;
g.addEdge(x-1, y-1, w);
}
g.dij(0);
}