#include <bits/stdc++.h>
#define Nmax 50005
#define INF (1 << 30)

using namespace std;

ifstream f("dijkastra.in");
ofstream g("dijkastra.out");

int n, m, i, j;
int used[Nmax];
bool in_stack[Nmax];

vector < pair <int,int> > v[Nmax];
struct comp
{
    bool operator()(int x, int y)
    {
        return used[x] > used[y];
    }
};

priority_queue<int, vector<int>, comp> Q;

void afisare()
{
    for ( i = 2 ; i <= n ; i++ )
    if ( used[i] != INF )
        g << used[i] <<" ";
       else
            g << "0" ;


}

void dijkastra(int node_start)
{
    for ( i = 1 ; i <= n ; i++ )
        used[i] = INF;

    used[node_start] = 0;

    Q.push(node_start);
    in_stack[node_start] = 1;

    while ( !Q.empty())
    {
        int cn = Q.top();
        Q.pop();

        int l = v[cn].size();
        for ( i = 0 ; i < l ; i++ )
        {
            int nn = v[cn][i].first;
            int cost = v[cn][i].second;
            if ( used[cn]+cost < used[nn] )
            {
                used[nn] = used[cn]+cost;
                if ( in_stack[nn] == 0 )
                {
                    Q.push(nn);
                    in_stack[nn] = 1;
                }
            }

        }
    }

}


int main()
{
    f >> n >> m;
    while ( m-- )
    {
        int x, y, c;
         f >> x >> y >> c;
         v[x].push_back({y, c});
    }

    dijkastra(1);
    afisare();

    return 0;
}