#include<cstdio>
#include<vector>
#include<queue>
#define _NMAX 50010
#define _MMAX 250010
#define INF 1<<30
using namespace std;

int nN, nM;
struct muchie
{
    int dest, cost;
};
vector<muchie > lAd[_NMAX];

int dist[_NMAX];
void bford();
int main()
{
    FILE *f=fopen("dijkstra.in", "r");
    fscanf(f, "%d %d", &nN, &nM);
    for (int i=1;i<=nM;i++)
    {
        int nod; muchie tmp;
        fscanf(f, "%d %d %d", &nod, &tmp.dest, &tmp.cost);
        lAd[nod].push_back(tmp);
    }
    bford(); //dist[]
    f=fopen("dijkstra.out", "w");
    for (int i=2;i<=nN;i++)
        fprintf(f, "%d ", dist[i]);
    return 0;
}

void bford()
{
    for (int i=2;i<=nN;i++) dist[i]=INF;
    dist[1]=0;
    queue<int > q;
    q.push(1);
    while (!q.empty())
    {
        int cur=q.front(); q.pop();
        for (int i=0; i<lAd[cur].size();i++)
        {
            muchie mcur=lAd[cur].at(i);
            if (dist[cur]+mcur.cost < dist[mcur.dest])
            {
                dist[mcur.dest] = dist[cur]+mcur.cost;
                q.push(mcur.dest);
            }
        }
    }
}