#include <fstream>
#include <vector>
#include <map>
#include <utility>
#include <queue>
 
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
 
const int INF=1<<28;
const int N=51000;
 
vector<pair <int,int> > graph[N];
int dist[N];
bool visited[N];
int vertices,edges;
 
inline void rint(int *a){
  register char c=0;while (c<33) c=getchar_unlocked();*a=0;
  while (c>33){*a=*a*10+c-'0';c=getchar_unlocked();}
}

void read(){
    rint(&vertices);
    rint(&edges);
    int x,y,c;
    for(int i=1;i<=edges;++i){
	rint(&x);
	rint(&y);
	rint(&c);        
        graph[x].push_back(make_pair(y,c));
    }
}
 
void Dijkstra(){
    int i;
    priority_queue< pair<int,int> > heap; // insert in the queue the distances with minus 
    for(int i=2;i<=vertices;++i){
        dist[i]=INF;
        visited[i]=false;
    }
    dist[1]=0;
    visited[1]=true;
    vector<pair <int,int> > ::iterator it;
    pair <int,int> currentpair;
    for(it=graph[1].begin();it!=graph[1].end();++it){
        currentpair=*it;
        heap.push(make_pair(-(currentpair.second),currentpair.first));
    }
    int unvisited=vertices-1,currentnode,currentdistance;
    while(unvisited && heap.empty()==false){
        while(visited[heap.top().second] && heap.empty()==false){
            heap.pop();
        }
        if(heap.empty()==true){
            break;
        }
        currentnode=heap.top().second;
        currentdistance=heap.top().first;
        dist[currentnode]=currentdistance;
        visited[currentnode]=true;
        heap.pop();
        unvisited--;
        for(it=graph[currentnode].begin();it!=graph[currentnode].end();++it){
            currentpair=*it;
            if(visited[currentpair.first]==false)
                heap.push(make_pair(currentdistance-(currentpair.second),currentpair.first));
        }
    }
    for(i=2;i<=vertices;++i){
        if(dist[i]==INF){
            dist[i]=0;
        }
        out<<-1*dist[i]<<" "; // le afisam cu minus pentru ca le-am bagat cu minus
    }
}
 
int main(){
    read();
    Dijkstra();
    return 0;
}