#include<bits/stdc++.h>
using namespace std;

FILE* in=fopen("dijkstra.in", "r");
FILE* out=fopen("dijkstra.out", "w");
const int INF=0x3f3f3f3f, NMAX=50007;
vector<pair<int, int> > G[NMAX];
int dist[NMAX];

int n, m;
void citire()
{
    fscanf(in, "%d%d", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        int nod, to, cost;
        fscanf(in, "%d%d%d", &nod, &to, &cost);
        G[nod].push_back(make_pair(to, cost));
    }
}

set<pair<int, int> > s;
void dijkstra()
{
    dist[1]=0;
    for(int i=2; i<=n; ++i) dist[i]=INF;
    s.insert(make_pair(1, 0));
    while(!s.empty())
    {
        int nod=s.begin()->first;
        int d=s.begin()->second;
        s.erase(s.begin());

        for(int i=0; i<G[nod].size(); ++i)
        {
            int to=G[nod][i].first;
            int cost=G[nod][i].second;
            if(dist[to]>cost+dist[nod])
            {
                if(dist[to]!=INF)
                    s.erase(s.find(make_pair(to, dist[to])));
                dist[to]=cost+dist[nod];
                s.insert(make_pair(to, dist[to]));
            }
        }
    }
}

int main()
{
    citire();
    dijkstra();

    for(int i=2; i<=n; ++i)
    {
        if(dist[i]==INF) dist[i]=0;
        fprintf(out, "%d ", dist[i]);
    }
}