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

using namespace std;

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define l 104*10
#define pb push_back

ifstream fin(IN);
ofstream fout(OUT);

int x , y , v , n , p , m;
int cost[50003];

vector<int>G[50003];
vector<int>C[50003];
queue<int>Q;

void Read()
{
    int i;

    fin >> n >> m;

    for ( i = 1 ; i <= m ; i ++ ){
            fin >> x >> y >> v;

            G[x].pb(y);
            C[x].pb(v);
    }

}

void Solve()
{
    int i;

    cost[1] = 0;
    Q.push(1);

    while (!Q.empty())
    {
        x = Q.front();

        for ( i = 0 ; i < G[x].size() ; i ++ )
            if ( cost[G[x][i]] == 0 or cost[G[x][i]] > cost[x] + C[x][i] )
        {
            cost[G[x][i]] = cost[x]+C[x][i];
            Q.push(G[x][i]);
        }

        Q.pop();
    }

    for ( i = 2 ; i <= n ; i ++ )
        fout << cost[i] << " ";
}

int main()
{

    Read();
    Solve();
}