#include <fstream>
#include <queue>

using namespace std;

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

queue < int > q;

void dfs ( int nod );

int n, m, i, x, y, c;
int a[3001][3001], r[50001];
bool viz[50001];

int main()
{
    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c;
        a[x][y] = c;
    }

    dfs ( 1 );

    for ( i = 2 ; i <= n ; i++ ) fout << r[i] << ' ';

    return 0;
}

void dfs ( int nod )
{
    q.push ( nod );
    while ( q.empty() == 0 )
    {
        x = q.front();
        q.pop();

        for ( i = 1 ; i <= n ; i++ )
            if ( a[x][i] != 0 &&  ( r[x] + a[x][i] < r[i] || r[i] == 0 ) )
            {
                r[i] = r[x] + a[x][i];
                q.push ( i );
                viz[x] = 1;
            }
    }
}