#include <cstdio>
#include <vector>
#include <queue>
#define NMax 50000
#define oo 1<<30
#define x first
#define y second
using namespace std;

typedef pair<int, int> per;
priority_queue<per> q;
vector<per> v[NMax+1];
int deja[NMax+1];
int d[NMax+1];

int main(){
    FILE* fin = fopen("dijkstra.in","r");
    FILE* fout = fopen("dijkstra.out","w");

    int i,N,M,A,B,C,D;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d %d",&A,&B,&C);
        v[A].push_back({B,C});
    }

    for(i = 2; i <= N; ++i) d[i] = oo;
    q.push({0,1});
    while(!q.empty())
    {
        C = -q.top().x;
        A = q.top().y;
        q.pop();
        if(!deja[A])
        {
            deja[A] = 1;
            for(i = 0; i < v[A].size(); ++i)
            {
                B = v[A][i].x;
                D = v[A][i].y;
                if(d[B] > d[A] + D){
                    d[B] = d[A] + D;
                    q.push({-d[B],B});
                }
            }
        }
    }

    for(i = 2; i <= N; ++i)
    if(d[i] != oo) fprintf(fout,"%d ",d[i]);
    else fprintf(fout,"0 ");


return 0;
}