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

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

void bford();

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);
    }
    bford();
    FILE *fout = fopen("dijkstra.out", "w");
    for (int i=2; i<=nN; i++)
        fprintf(fout, "%d ", dist[i]==1<<30?0:dist[i]);
    return 0;
}

void bford()
{
    dist[1]=0;
    for (int i=2;i<=nN;i++)
        dist[i]=1<<30;

    for (int i=1; i<=nN-1; i++)
        for (int j=1; j<=nN; j++)
            for (int k=0; k<lAd[j].size(); k++)
            {
                int curnod1=j;
                int curnod2=lAd[j].at(k).nod;
                int costmuchie12=lAd[j].at(k).cost;
                if (dist[curnod1]+costmuchie12<dist[curnod2])
                    dist[curnod2]=dist[curnod1]+costmuchie12;
            }
}