#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_SIZE = 5005;
const int INF = (1 << 30);

int n,m;
int D[MAX_SIZE];
bool check[MAX_SIZE];
vector<pair<int,int> >G[MAX_SIZE];

struct compar{
    bool operator()(int x,int y){
        return D[x] > D[y];
    }
};

priority_queue<int, vector<int>, compar> P_Queue;


void read(){

    fstream in("dijkstra.in",ios::in);
    in >> n >> m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        in >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
}

int fout(int value){
    return value == INF ? 0 : value;
}

void write(){
    fstream out("dijkstra.out",ios::out);
    for(int i=2;i<= n;i++)
        out << fout(D[i]) << " ";
    out.close();
}

void dijkstra(int nod){
    for(int i=1;i<=n;i++)
        D[i] = INF;
    D[nod] = 0;
    P_Queue.push(nod);
    check[nod] = true;
    while(!P_Queue.empty()){
        int nodSet = P_Queue.top();
        P_Queue.pop();
        check[nodSet] = false;

        for(size_t i = 0;i < G[nodSet].size();++i){
            int neighbor = G[nodSet][i].first;
            int cost = G[nodSet][i].second;
            if(D[neighbor] > D[nodSet] + cost){
                D[neighbor] = D[nodSet] + cost;
                if(check[neighbor] == false){
                    check[neighbor] = true;
                    P_Queue.push(neighbor);
                }
            }
        }
    }
}

int main()
{
    read();
    dijkstra(1);
    write();
    return 0;
}