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

#define INF 0x3f3f3f3f
#define NMAX 50005
using namespace std;



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


struct compara
{

    const bool operator () ( const pair<int,int>& p1 , const pair<int,int>& p2 ) const
    {

        return p1.second>p2.second;
    }


};



vector < pair <int,int>  > v[50002];

priority_queue < pair <int, int> > q;




int d[NMAX];




int main()
{
    int n,m;
    int nod1,nod2,cost;
    int i,sze,fiu,c;

    in>>n>>m;

    for(i=1; i<=m; ++i)
    {

        in>>nod1>>nod2>>cost;
        v[nod1].push_back(make_pair(nod2,cost));

    }


    for(i=2; i<=n; ++i)
        d[i]=INF;


    pair <int,int > temp;

    temp.first=1;
    temp.second=0;

    q.push(temp);


    while(!q.empty())
    {

        temp=q.top();
        q.pop();

        sze=v[temp.first].size();

        for(i=0; i<sze; ++i)
        {

            fiu=v[temp.first][i].first;

            c=temp.second+v[temp.first][i].second;

            if(d[fiu]>c)
            {
                d[fiu]=c;
                q.push(make_pair(fiu,d[fiu]));

            }





        }


    }


    for(int i = 2; i <= n; i++)
    {
        if(d[i] == INF)
            d[i] = 0;
        out<<d[i]<<' ';
    }



    return 0;


}