#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

#define nmax 50010
#define muchie pair<long, pair<long,long> >
#define cost first
#define start second.first
#define end second.second
struct other
{
       long endd,costt;
};
struct edge
{
       vector<other> neighbour;
};
edge nodes[nmax];
vector<long> used(nmax);
vector<long> dist(nmax,10000);

long n,m,a,b,c;
priority_queue<muchie, vector<muchie>, greater<muchie> >q;

void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             scanf("%ld %ld %ld", &a,&b,&c);
             other New;
             New.endd=b;
             New.costt=c;
             nodes[a].neighbour.push_back(New);
     }
}

void Dijkstra(long st)
{
     dist[st]=0;
     int nr=1;
     do
     {
         used[st]=1;
         for(int i=0;i<nodes[st].neighbour.size();i++)
         {
                 if(used[nodes[st].neighbour[i].endd]==0)
                 {
                          //printf("st=%ld end=%ld\n", st,nodes[st].neighbour[i].endd);
                          q.push(make_pair(nodes[st].neighbour[i].costt+dist[st],make_pair(st,nodes[st].neighbour[i].endd)));
                 }
         }
         if(q.size())
         {
            muchie old=q.top();
            q.pop();
            if(old.cost<dist[old.end])
            { 
                                      //printf("dist[%ld]=%ld\n", old.end,old.cost); 
                                      dist[old.end]=old.cost;
                                      st=old.end;
                                      nr++;
            }
         }else
         {
              break;
         }
     }while(nr<=n);
     for(int i=2;i<=n;i++)if(dist[i]==10000)printf("0 ");else printf("%ld ", dist[i]);
     printf("\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    //int i;
    read_input();
    Dijkstra(1);
    //scanf("%i", &i);
    return 0;
}