#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int NMAX = 50005;
const int INF = 250000000;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

vector<ii> G[NMAX+5];

int main()
{
    int i, n, m, u, v, w, s;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; ++i){
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(ii(v,w));
    }
    s = 1;
    vi dist(n+1, INF);
    dist[s] = 0;
    priority_queue< ii, vector<ii>, greater<ii> > pq;
    pq.push(ii(0,s));

    while(!pq.empty()){

        ii front = pq.top();
        pq.pop();
        int d = front.first, u = front.second;
        if(d > dist[u])
            continue;
        for(int j = 0; j < (int)G[u].size(); ++j){
            int v = G[u][j].first, duv = G[u][j].second;
            if(dist[u] + duv < dist[v]){
                dist[v] = dist[u] + duv;
                pq.push(ii(dist[v], v));
            }
        }
    }
    for(int i = 2; i <= n; ++i){
        if(dist[i] == INF)
            dist[i] = 0;
        printf("%d ", dist[i]);
    }
    return 0;
}