#include <cstdio>
//ATENTIE LA CITIRE!!!
#include <vector>
#include <cstring>
#include <queue>
#define nmax 50001
#define infile "dijkstra.in"
#define outfile "dijkstra.out"

using namespace std;

vector< pair<int, int> > gf[nmax];
int d[nmax], n, m;
queue<int> Q;

void dijkstra(int sursa){
    memset(d,nmax,sizeof(d));//initializeaza vectorul d cu valoare inf pe toata lungimea lui;
    d[sursa]=0;

    for(Q.push(sursa);Q.size();Q.pop()){
        int nod = Q.front();
        for(vector< pair<int,int> >:: iterator it=gf[nod].begin();it!=gf[nod].end();it++){
            int y = it->first;
            int c = it->second;
            if (d[y] > d[nod] + c){
                d[y] = d[nod] + c;
                Q.push(y);
            }
        }
    }

}

int main(){

    freopen(infile,"r",stdin);
    freopen(outfile,"w",stdout);
    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y, c;
        scanf("%d %d %d\n", &x, &y, &c);
        gf[x].push_back(make_pair(y,c));
    }

    int sursa = 1;

    dijkstra(sursa);

    for(int i=2; i<=n; i++) printf("%d ", d[i]);

    return 0;
}