#include <stdio.h>
#include <vector>
#include <list>
#include <set>

using namespace std;

const int INF=1<<30;

int main()
{
    FILE *f;
    int n,m,a,b,c,i,nod;
    vector<list<pair<int,int> > > L;
    vector<int> D;
    vector<bool> viz;
    set<pair<int,int> > Q;

    f=fopen("dijkstra.in","r");
    fscanf(f,"%d%d",&n,&m);
    L.resize(n+1);
    D.resize(n+1);
    for (i=0; i<m; i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        L[a].push_back({c,b});
    }
    fclose(f);

    viz.resize(n+1,false);
    for (i=1; i<=n; i++)
        D[i]=INF;
    D[1]=0;
    Q.insert({0,1});
    while (!Q.empty())
    {
        nod=Q.begin()->second;
        Q.erase((Q.begin()));
        if (!viz[nod])
        {
            viz[nod]=true;
            for (list<pair<int,int> >::iterator x = L[nod].begin(); x != L[nod].end(); x++)
            {
                if (D[nod] + x->first < D[x->second])
                {
                    D[x->second]=D[nod]+x->first;
                    Q.insert({D[x->second],x->second});
                }
            }
        }
    }

    f=fopen("dijsktra.out","w");
    for (i=2; i<=n; i++)
        if (D[i] == INF)
            fprintf(f,"0 ");
        else
            fprintf(f,"%d ",D[i]);
    fclose(f);

    return 0;
}