#include <cstdio>
#include <set>
#include <vector>
#include <cstring>

#define NMAX 50005
#define INF 0x3f3f3f3f
using namespace std;
vector < pair<int,int> > G[NMAX];
set < pair<int,int> > Q;
int D[NMAX],N,M,i,x,y,z;

void dijkstra(int nod)
{
    D[nod]=0;
    Q.insert(make_pair(nod,0));

    while (!Q.empty())
    {
        int k = (*Q.begin()).first;
        int cost = (*Q.begin()).second;
        Q.erase(*Q.begin());
        for (vector < pair<int,int> > :: iterator itt=G[k].begin(); itt != G[k].end(); ++itt)
            if (D[itt->first] > cost + itt->second)
            {
                D[itt->first] = cost + itt->second;
                Q.insert(make_pair(itt->first, D[itt->first]));
            }
    }
}

int main()
{
    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", &x, &y, &z);
        G[x].push_back(make_pair(y,z));
    }

    memset(D,INF,sizeof(D));
    dijkstra(1);
    for (i=2; i<=N; i++)
        if (D[i]==INF) printf("0 ");
        else printf("%d ", D[i]);
}