#include <fstream>
#include <vector>
using namespace std;
#define inf 200000000
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

vector <int> A[50001];
vector <int> C[50001];
int n, d[50001], viz[50001];

int main()
{
    int m, i, x, y, c, nod, mi;
    fi >> n >> m;
    for( i = 1; i <= m; i++ ){
        fi >> x >> y >> c;
        A[x].push_back(y);
        C[x].push_back(c);
        d[i] = inf;
    }
    d[1] = 0;
    for( i = 0; i < A[1].size(); i++ )
        d[A[1][i]] = C[1][i];

    while( mi != inf ){
        mi = inf;
        for( i = 1; i <= n; i++ )
            if( d[i] < mi && viz[i] == 0 ){
                mi = d[i];
                nod = i;
            }
        if( mi < inf ){
            viz[nod] = 1;
            for( i = 0; i < A[nod].size(); i++ )
                if( d[A[nod][i]] > d[nod] + C[nod][i] && viz[A[nod][i]] == 0 )
                    d[A[nod][i]] = d[nod] + C[nod][i];
        }
    }

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

    return 0;
}