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

using namespace std;
typedef pair<int , int > pereche;
int vdi[50001];
int viz[50001];

struct comparator {
 bool operator()(pair<pereche,int> i,pair<pereche,int>  j) {
 return i.second > j.second;
 }
};
priority_queue< pair<pereche,int>, std::vector<pair<pereche,int> >, comparator> minHeap;
class graf
{   int n , m,c;
    vector <pair<int,int> > A[50000];
public:


    void citire(char *numfis)
    {  int i;
        ifstream f(numfis);
        f>>n;
        f>>m;
        for(i=0;i<m;i++)
        {   int a ,b,c;
            f>>a>>b>>c;
            A[a].push_back(make_pair(b,c));



        }
    }
    void afisare()
    {  int i , j;
        for(i=1;i<=n;i++)
        {   cout<<"\n"<<i<<": ";
            for(j=0;j<A[i].size();j++)
                cout<<A[i][j].first<<" ";
        }
    }
    void actualizare(int cost_actual,int costdupa,int nod)
    {
        vdi[nod]=costdupa;
        for(int i=0;i<A[nod].size();i++)
        {
            int a=vdi[A[nod][i].first];
            vdi[A[nod][i].first]=costdupa+A[nod][i].second;
            actualizare(a,vdi[A[nod][i].first],A[nod][i].first);
        }
    }

    void Dijkstra()
      {
         int i;
         pair <pereche,int> pdp,pdp2;
         graf A;
         viz[1]=1;
         for(i=0;i<this->A[1].size();i++)
         {
            pdp=make_pair(make_pair(1,this->A[1][i].first),this->A[1][i].second);
            minHeap.push(pdp);
         }
         pdp=minHeap.top();
         while(!minHeap.empty())
         {
            int ok=0;
            pdp=minHeap.top();
            if(viz[pdp.first.first] && viz[pdp.first.second]==0)
                {   this->A[pdp.first.first].push_back(make_pair(pdp.first.second,pdp.second));
                    vdi[pdp.first.second]=vdi[pdp.first.first]+pdp.second;
                    viz[pdp.first.second]=pdp.first.first;
                     minHeap.pop();
                       for(i=0;i<this->A[pdp.first.second].size();i++)
                       {
                           if(viz[this->A[pdp.first.second][i].first]==0)
                           {
                           pdp2=make_pair(make_pair(pdp.first.second,this->A[pdp.first.second][i].first),this->A[pdp.first.second][i].second);
                           minHeap.push(pdp2);
                           }
                       }
                }
            else
                if(viz[pdp.first.second]&& viz[pdp.first.first]==0)
                   {
                       this->A[pdp.first.second].push_back(make_pair(pdp.first.first,pdp.second));
                       vdi[pdp.first.first]=vdi[pdp.first.second]+pdp.second;
                       viz[pdp.first.first]=pdp.first.second;
                        minHeap.pop();
                       for(i=0;i<this->A[pdp.first.first].size();i++)
                       {
                           if(viz[this->A[pdp.first.first][i].first]==0)
                           {pdp=make_pair(make_pair(pdp.first.first,this->A[pdp.first.first][i].first),this->A[pdp.first.first][i].second);
                           minHeap.push(pdp);}
                       }
                   }
                   else
                   {
                       if(vdi[pdp.first.first]+pdp.second <vdi[pdp.first.second])
                         vdi[pdp.first.second]=vdi[pdp.first.first]+pdp.second;
                         else
                           if(vdi[pdp.first.second]+pdp.second<vdi[pdp.first.first])
                           vdi[pdp.first.first]=vdi[pdp.first.second]+pdp.second;
                       minHeap.pop();
                   }


         }
         ofstream g("dijkstra.out");
         for(i=2;i<=this->n;i++)
            g<<vdi[i]<<" ";

       }




};

int main()
{   graf G;
    ifstream f("dijkstra.in");
    G.citire("dijkstra.in");

    G.Dijkstra();
}