#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

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

const int N=250002;
int d[N],n,m,xs;
priority_queue < pair < int, int> > h;
vector < pair < int, int> >a[N];
bool sel[N];

void citire()
{
     int x,y,l;
     in>>n>>m;
     for(int i=1;i<=m;i++)
     {
         in>>x>>y>>l;
         a[x].push_back(make_pair(y,l));
     }
}

void dijkstra(int x0)
{
     int inf = 1 << 30;
     for(int i=1; i<=n; i++)
     {
         d[i]=inf;
     }
     d[x0]=0;
     h.push(make_pair(-d[x0],x0));
     while(!h.empty())
     {
           while(!h.empty() && sel[h.top().second])
           {
                 h.pop();
           }
           if(h.empty())
           {
              return;
           }
           int x=h.top().second;
           sel[x]=true;
           for(auto p:a[x])
           {
               int y=p.first;
               int c=p.second;
               if(d[x]+c<d[y])
               {
                  d[y]=d[x]+c;
                  h.push(make_pair(-d[y],y));
               }

           }
      }
}

int main()
{
    citire();
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        out<<d[i]<<' ';
    }
    return 0;
}