#include<cstdio>
#include<vector>
#include<queue>

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



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[NMAX];

priority_queue < pair <int, int> > q;




int d[NMAX];




int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);



    int n,m;
    int nod1,nod2,cost;
    int i,sze,fiu,c;

    scanf("%d%d",&n,&m);

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

        scanf("%d%d%d",&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)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }


    return 0;


}