#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream f1("dijkstra.in");
ofstream f2("dijkstra.out");
#define NMAX 50101
#define INF 1000000006

int n, m, d[NMAX];
vector<int> Graf[NMAX], Cost[NMAX];
set< pair<int,int> > S;

void solve()
{
    int i,  val, x;

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

    S.insert( make_pair(0,1) );

    while ( S.size() > 0 )
    {
        val= (*S.begin()).first;
        x= (*S.begin()).second;

        S.erase(*S.begin());

        for (i=0; i< Graf[x].size(); i++ )
            if ( d[ Graf[x][i] ] > val + Cost[x][i] )
            {
                d[ Graf[x][i] ]= val + Cost[x][i];
                S.insert( make_pair( d[Graf[x][i] ], Graf[x][i] ) );
            }
    }

}

int main()
{
    int i, x, y, c;

    f1>>n>>m;

    for (i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        Graf[x].push_back(y);
        Cost[x].push_back(c);
    }

    solve();

    for (i=2; i<=n; i++)
        if ( d[i] == INF )
            f2<<"0 ";
        else
            f2<<d[i]<<" ";

    return 0;
}