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

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

struct dist_bigger
{
    bool operator() (int a,int b)
    {
        return dist[a]>dist[b];
    };
};
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]==1<<30?0:dist[i]);
    return 0;
}

void dijkstra()
{
    std::priority_queue<int ,vector<int >, dist_bigger > q;
    for (int i=1; i<=nN; i++) q.push(i);

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

    while (!q.empty())
    {
        int cur=q.top(); 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);
            }
        }
    }
}