#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int haha=1000000000;
struct Nod {
  unsigned short int n;
  int d;
};

struct cmp {
  bool operator()(const Nod& a, const Nod& b) const
  {return (a.d > b.d);}
};
vector<int> V[50001],C[50001];
int i,n,d[50001],selectat[50001];
Nod nod;
priority_queue<Nod,vector<Nod>,cmp> p;
void dij(int sur)
{
    int nmin,dn,vecin;
    for(i=2;i<=n;i++)
        d[i]=haha;
    d[sur]=0;
    nod.n=1; nod.d=0; p.push(nod);
    while(!p.empty())
    {
        nod=p.top(); p.pop();
        nmin=nod.n;
        if(!selectat[nmin])
        {
            selectat[nmin]=1;
            for (size_t i=0;i<V[nmin].size();i++)
            {
               vecin=V[nmin][i];
               if(!selectat[vecin])
               {
                   dn=d[nmin]+C[nmin][i];
                   if(d[vecin]>dn)
                   {
                       d[vecin]=dn;
                       nod.n=vecin; nod.d=dn; p.push(nod);
                   }
               }
            }
        }
    }
}
int main()
{
    int x,y,m,c;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        V[x].push_back(y);
        f>>c;
        C[x].push_back(c);
    }
    dij(1);
    for(i=2;i<=n;i++)
     if(d[i]!=haha) g<<d[i]<<" ";
        else g<<0<<" ";
    return 0;
}