#include <iostream>
#include <fstream>
#include <set>
#include <cstring>
#include <vector>
#define dim 250005
#define INF 0x3f3f3f3f
using namespace std;

vector <pair<int,int> >G[dim];
int n,m,x,y,c,dist[dim];

void read();
void dijkstra();


int main()
{
    read();
    dijkstra();

    fstream fout("dijkstra.out",ios::out);

    for(int i=2;i<=n;++i){

        if(dist[i] == INF)
            dist[i] = 0;
        fout << dist[i] << " ";
    }

    fout.close();

    return 0;
}


void read(){

    fstream fin("dijkstra.in",ios::in);

    fin >> n >> m;

    for(int i=1;i<=m;++i){

        fin >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
}

void dijkstra(){

    set<pair<int,int> > Set;
    memset(dist,INF,sizeof(dist));
    Set.insert(make_pair(0,1));
    dist[1] = 0;

    while(!Set.empty()){

        int node = Set.begin()->second;
        int distance = Set.begin()->first;
        Set.erase(Set.begin());

        for(vector<pair<int,int> >::iterator it=G[node].begin(); it != G[node].end(); ++it){
            int y = it->first;
            int c = it->second;

            if(dist[y] > dist[node] + c){

                if(dist[y] != INF)
                    Set.erase(Set.find(make_pair(dist[y],y)));
                dist[y] = dist[node] + c;
                Set.insert(make_pair(dist[y],y));
            }
        }
    }
}