#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#define Nmax 50005
#define oo (1<<30)


using namespace std;


int D[Nmax],n,m;
bool viz[Nmax];
vector < pair <int , int> > graph[Nmax];
struct comparisonFunc
{
    bool operator()(int x,int y)
    {
        return D[x] > D[y];
    }
};
priority_queue < int , vector < int > , comparisonFunc > minHeap;


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


void Dijkstra(int startNode)
{
    for(int i = 1;i <= n; i++) {
    D[i]=oo;
}
    D[startNode]=0;
    minHeap.push(startNode);
    viz[startNode]=1;


    while(!minHeap.empty()) {
        int nod = minHeap.top();
        minHeap.pop();
        viz[nod]=0;
        for(unsigned int i=0; i<graph[nod].size(); i++) {
            int vecin = graph[nod][i].first;
            int cost = graph[nod][i].second;
            if(D[nod]+cost < D[vecin]) {  
               
               D[vecin] = D[nod]+cost;
               if(viz[vecin] == 0) {
                   viz[vecin] = 1;
                   minHeap.push(vecin);
               }
           }
        }
    }
}
int main() {    
   in>>n>>m;
for(int i = 1; i <= m; i++){  
   int x,y,c;
   in>>x>>y>>c;
   graph[x].push_back(make_pair(y,c));
}

Dijkstra(1);

for(int i=2;i<=n;i++) {
    if(D[i]!=oo) {
	out<<D[i]<<' ';
    }
    else out<<0<<' ';
}

    return 0;
}