#include <fstream>
#include<vector>

#define nmax 50073
#define left_son (nod << 1)
#define right_son (left_son) + 1

const static int infinit=1 << 30;

using namespace std;

typedef struct
{
    int nod2;
    int dis;
}pereche;

int viz[nmax], dist[nmax],n;
vector <pereche> v[nmax];
pair <int,int> hmin[1<<17];

using namespace std;

void vecini(int &nod1,int &nod2, int &dis)
{
    pereche p;
    p.nod2=nod2;
    p.dis=dis;

    v[nod1].push_back(p);
}

pair <int,int> el_min(int &nod)
{
    if (hmin[left_son].second<hmin[right_son].second) return hmin[left_son];


    else return hmin[right_son];

}

void update(int nod, int left, int right,const int &pos, const int &el)
{
    if (left==right)
    {
        hmin[nod].second=el;
        hmin[nod].first=pos;
        return;
    }


    int mid=(left+right) >> 1;
    if (pos<=mid) update(left_son,left,mid,pos,el);
    else update(right_son,mid+1,right,pos,el);

    hmin[nod]=el_min(nod);


}


void distante(int &a, int &b, int &c)
{

    int  distance=dist[a]+c;
    if (dist[b]>distance)  {
                              dist[b]=distance;
                              update(1,1,n,b,distance);
                           }
}

void parcurgere()
{
   int nod;
   update(1,1,n,1,0);
   for (int j=1;j<=n;j++)
   {
        nod=hmin[1].first;
        viz[nod]=1;
        update(1,1,n,nod,infinit);

        for (unsigned int i=0;i<v[nod].size();i++)
            if (!viz[v[nod][i].nod2]) distante(nod,v[nod][i].nod2,v[nod][i].dis);
   }

}


int main()
{

    int a,b,c,m;

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;

    for (int i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            vecini(a,b,c);
        }


    for (int i=2;i<=n;i++)
        dist[i]=infinit;

    fill(hmin,hmin+(1<<17),make_pair(1,infinit));

    dist[1]=0;

    parcurgere();

    for (int i=2;i<=n;i++)
       if (dist[i]==infinit)  cout<<0<<" ";
            else  cout<<dist[i]<<" ";

    cin.close();
    cout.close();
   return 0;
}