#include <fstream>
#include <vector>
#include <set>
#define DIM 100002
#define INF 1e9

using namespace std;

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

int n, x, y, d, m;
int dist[DIM];

bool inQueue[DIM];

vector<pair<int, int> > graf[DIM];

class compare{
public:
    bool operator() (int a, int b){
        return dist[a] < dist[b];
    }
};

set<pair<int, int> > s;

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y>>d;
        graf[x].push_back({y, d});
        
    }
    dist[1] = 0;
    for(int i = 2; i <= n; ++ i)
        dist[i] = INF;
    
    inQueue[1] = true;
    s.insert({0, 1});
    
    while(!s.empty()){
        int currNode = s.begin()->second;
        s.erase(s.begin());
        for(auto it : graf[currNode]){
            int nextNode = it.first;
            int distance = it.second;
            if(dist[currNode] + distance < dist[nextNode]){
                s.erase({dist[nextNode], nextNode});
                dist[nextNode] = dist[currNode] + distance;
                s.insert({dist[nextNode], nextNode});
            }
        }
    }
    
    for(int i = 2; i <= n; ++ i){
        if(dist[i] == INF)
            out<<"0 ";
        else
            out<<dist[i]<<" ";
        
    }
    
    
    
    return 0;
}