#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
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;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");


void read_input()
{
     in>>n>>m;
     //scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             //scanf("%ld %ld %ld", &a,&b,&c);
             in>>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) out<<0<<' ';else out<<dist[i]<<' ';
     out<<'\n';
}

int main()
{
    //int i;
    read_input();
    Dijkstra(1);
    //scanf("%i", &i);
    in.close();
    out.close();
    return 0;
}