#include<fstream>
#include<vector>
#include<queue>
#define inf 999999999999999999

using namespace std;

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

struct per
{
    int val;
    long long cost;
};

struct nod
{
    int val;
    friend bool operator< (nod n1, nod n2);
};

int n,m,x,y,i; bool viz[50001];
short c;
per p, perCurenta; nod newNode, acestNod, nodCurent;
vector<per> v[50001];
priority_queue<nod> heap;
long long dist[50001];

bool operator< (nod n1, nod n2)
{
    return dist[n1.val]>dist[n2.val];
}

int main()
{
    f>>n>>m;
    for(i=0;i<m;i++)
    {
       f>>x>>y>>c;
       p.val=y-1;p.cost=c;
       v[x-1].push_back(p);
       if(x==1)
          {newNode.val=y-1; dist[y-1]=c; heap.push(newNode); viz[y-1]=1; }
    }

    for(i=1;i<n;i++)
    {
       if(!viz[i])
       {
           newNode.val=i; dist[i]=inf; heap.push(newNode);
       }
       else
         viz[i]=0;

    }

  while(!heap.empty())
  {
    acestNod=heap.top();
    heap.pop();

       if(acestNod.val==inf)
            break;

       for(i=0;i<v[acestNod.val].size();i++)
       {
           perCurenta=v[acestNod.val][i];
           if(dist[perCurenta.val]>perCurenta.cost+dist[acestNod.val])
           {
               dist[perCurenta.val]=perCurenta.cost+dist[acestNod.val];
               newNode.val=perCurenta.val;
               heap.push(newNode);
           }
       }
   }

   for(i=1;i<n;i++)
     if(dist[i]==inf)
       g<<0<<" ";
     else
       g<<dist[i]<<" ";

   f.close();g.close();
   return 0;

}