#include <fstream>
#include <vector>
#include <utility>
#include <set>


#define nmax 50005
#define inf 0x3f3f3f3f
using namespace std;

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

set<pair<int,int> >heap;
vector<pair<int,int> >a[nmax];
vector<pair<int,int> >::iterator it;
int n, m, d[nmax];

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

void dijsktra()
{
    int i, c, nod, next;
      for(i=1;i<=n;i++)
        d[i]=inf;
        d[1]=0;
        heap.insert(make_pair(0,1));
        while(!heap.empty())
        {
            c=heap.begin()->first;
            nod=heap.begin()->second;
            heap.erase(heap.begin());
        for(it=a[nod].begin();it!=a[nod].end();it++)
        {
              next=it->first;
              c=it->second;
               if(d[next]>d[nod]+c)
               {
                    if(d[next]!=inf)
                         heap.erase(heap.find(make_pair(d[next],next)));
                    d[next]=d[nod]+c;
                    heap.insert(make_pair(d[next],next));
               }
        }

    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            d[i]=0;
        g<<d[i]<<' ';
    }
}
int main()
{
    citire();
    dijsktra();
    return 0;

}