#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
/// Se da un graf neorientat cu n noduri si m muchii. Sa se afiseze toate componentele conexe din graful respectiv.-BFS

#define NMAX 50005
struct nod
{
    int c,y;
};

struct cmp
{
    bool operator()(const nod a,const nod b)
    {
       return a.c > b.c;
    }
};

vector <nod> g[NMAX];
priority_queue <nod, vector<nod> , cmp> q;
int d[NMAX];

void functie()
{
    nod x;
    x.y=1;
    x.c=0;
    q.push(x);
    int s;

    while(!(q.empty()))
   {
        s=q.top().y;
        q.pop();
        for(int j=0; j<g[s].size(); j++)
        {
            if(d[g[s][j].y]>d[s]+g[s][j].c)
           {
               x.y=g[s][j].y;
               x.c=d[s]+g[s][j].c;
               q.push(x);
               d[g[s][j].y]=d[s]+g[s][j].c;
           }
        }
   }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m, a, b, c;
    nod x;
    scanf("%d %d \n", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d \n", &a,&b,&c);
        x.y=b;
        x.c=c;
        g[a].push_back(x);
    }

    for(int i=2; i<=n; i++) d[i]=NMAX;
    functie();
    for(int i=2; i<=n; i++) cout<<d[i]<<" ";


    return 0;
}