#include<stdio.h>
#include<vector>
#include<set>
#include<list>
#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];
//set<nod> uber;
list<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);
    uber.push_back(p);

    while(uber.size()>0)
    {
        int c=(*uber.begin()).first;
        int s=(*uber.begin()).second;
        uber.erase(uber.begin());
        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]));
            }
    }

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