#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;
     for(int i=0;i<m;i++)
     {
             in>>a>>b>>c;
             // adaug muchia de la a la b cu costul c
             other New;
             New.endd=b;
             New.costt=c;
             nodes[a].neighbour.push_back(New);
     }
}

void Dijkstra(long st)
{
     dist[st]=0; // distanta startului e 0
     int nr=1;
     do
     {
         used[st]=1;  //marchez startul ca folosit
         for(int i=0;i<nodes[st].neighbour.size();i++)
         {
                 if(used[nodes[st].neighbour[i].endd]==0)   // pt vecinii nevizitati ai start-ului
                 {
                          //adaug in coada de prioritati muchia
                          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();      // scot muchia de cost minim
            if(old.cost<dist[old.end])    // actualizez distanta end-ului daca e cazul 
            {  
                                      dist[old.end]=old.cost;
                                      st=old.end;
                                      nr++;
            }
         }else
         {
              break;
         }
     }while(nr<=n);   // cat timp nu am distantele pt toate nodurile
     for(int i=2;i<=n;i++)if(dist[i]==10000) out<<0<<' ';else out<<dist[i]<<' ';
     out<<'\n';
}

int main()
{
    read_input();
    Dijkstra(1);
    in.close();
    out.close();
    return 0;
}