#include<stdio.h>
#include<vector>
#include<vector>
#include<algorithm>
#define INF 50001
#define MAX 1410065407
#define nod pair<int,int>

using namespace std;
//using namespace __gnu_cxx;

int n,m;
vector<int> graph[INF],cost[INF];
int dist[INF];
vector<nod> uber;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=0;i<m;i++)
    {
        int s,d,c;
        scanf("%d %d %d\n",&s,&d,&c);
        graph[s].push_back(d);
        cost[s].push_back(c);
    }

    for(int i=2;i<=n;i++)dist[i]=MAX;
    nod p = make_pair(0,1);
    //uber.insert(p);
    make_heap(uber.begin(),uber.end());

    uber.push_back(p);
push_heap(uber.begin(),uber.end());

    while(uber.size()>0)
    {
       int c=(*uber.begin()).first;
       int s=(*uber.begin()).second;
       /*int c=uber.top().first;
       int s=uber.top().second;*/
       pop_heap(uber.begin(),uber.end());
        uber.pop_back();

        for(int i=0;i<graph[s].size();i++)
            if(dist[graph[s][i]]>cost[s][i]+c)
            {
               dist[graph[s][i]]= cost[s][i]+c;
              // uber.insert(make_pair(dist[graph[s][i]],graph[s][i]));

              uber.push_back(make_pair(dist[graph[s][i]],graph[s][i]));
              push_heap(uber.begin(),uber.end());

            }
    }

    for(int i=2;i<=n;i++)if(dist[i]!=MAX)printf("%d ",dist[i]);
    else printf("0 ");
    printf("\n");
}