#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#define INF 0x3f3f3f3f
#define DIM 50005
using namespace std;

FILE *fin = freopen("dijkstra.in","r",stdin);
FILE *fout = freopen("dijkstra.out","w",stdout);

int N, M;
set<pair<int,int> > SET;
vector<pair<int, int> > v[DIM];

void dijkstra(int);

int main()
    {
        scanf("%d%d", &N, &M);

        int X, Y, Z;
        for (int i = 1; i <= M; i++)
        {
            scanf("%d%d%d", &X, &Y, &Z);
            v[X].push_back(make_pair(Y, Z));
        }

        dijkstra(1);
    }

void dijkstra(int x)
{
    int w[DIM];

    memset(w, INF, sizeof(w));

    w[x] = 0;
    SET.insert(make_pair(0, x));

    while (SET.size())
    {
        int nod = (*SET.begin()).second;

        SET.erase(*SET.begin());

        for (int i = 0; i < v[nod].size(); i++)
            if (w[v[nod][i].first] > v[nod][i].second + w[nod])
            {
                w[v[nod][i].first] = v[nod][i].second + w[nod];
                SET.insert(make_pair(w[v[nod][i].first], v[nod][i].first));
            }
    }

    for (int i = 2; i <= N; i++)
        if (w[i] == INF)
            printf("0 ");
        else
            printf("%d ", w[i]);
}