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

int nN, nM;
struct muchie
{
    int nod,cost;
};
vector<muchie > lAd[50000];
int dist[50000];

void dijkstra();

int main()
{
    FILE *fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d %d", &nN, &nM);

    int inod1,inod2,icost;
    for (int i=1; i<=nM; i++)
    {
        fscanf(fin, "%d %d %d", &inod1, &inod2, &icost);
        muchie tmp;
        tmp.nod=inod2; tmp.cost=icost;
        lAd[inod1].push_back(tmp);
    }
    dijkstra();
    FILE *fout = fopen("dijkstra.out", "w");
    for (int i=2; i<=nN; i++)
        fprintf(fout, "%d ", dist[i]);
    return 0;
}

void dijkstra()
{
    queue<int > q; q.push(1);

    dist[1]=0;
    for (int i=2;i<=nN;i++)
        dist[i]=1<<30; //infinity

    while (!q.empty())
    {
        int cur=q.front(); q.pop();
        for(int i=0;i<lAd[cur].size();i++)
        {
            muchie veccur=lAd[cur].at(i);
            if (dist[cur]+veccur.cost < dist[veccur.nod])
            {
                dist[veccur.nod] = dist[cur]+veccur.cost;
                q.push(veccur.nod);
            }
        }
    }

}