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

#define f first
#define s second
#define INF 2000000000
/*
#define curSiz v[Q.front()].size()
#define curAsc v[Q.front()][i].first
#define curCost v[Q.front()][i].second
#define curPoz Q.front()
*/

using namespace std;

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

vector < pair <int,int> > v[50010];
queue <int> Q;
int a,b,x,y,c,n,m,i,curSiz,curAsc,curCost,curPoz;
pair <int,int> nxt;
int ans[50010];

int main()
{
    fin>>n>>m;
    for(i=1 ; i<=m ; ++i)
    {
        fin>>x>>y>>c;
        nxt.f = y;
        nxt.s = c;
        v[ x ].push_back(nxt);
    }

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


    Q.push( 1 );
    while( !Q.empty() )
    {
        curSiz = v[ Q.front() ].size();

        for(i=0 ; i<curSiz ; ++i)
        {
            curAsc = v[Q.front()][i].first;
            curCost = v[Q.front()][i].second;
            curPoz = Q.front();
            if( ans[curAsc] > ans[curPoz] + curCost )
            {
                ans[curAsc] = ans[curPoz] + curCost;
                Q.push( curAsc );
            }
        }

        Q.pop();
    }
    for(i=2 ; i<=n ; ++i)
        if( ans[ i ] == INF)
            fout<<0<<' ';
        else
            fout<<ans[ i ]<<' ';


return 0;
}