#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
FILE *f,*g;

int v[50002],cost[250002],t[2][250002],n,start[50002];
bool viz[50002];

struct name
{
    int a,b;
};

class compar
{
public:
    bool operator() (name A, name B)
    {
        return (A.b>B.b);
    }
};

priority_queue <name , vector <name>, compar> q;

void d(int nod)
{
    int vecin,poz;
    q.push({1,0});
    while(!q.empty())
    {
        name da;
        da=q.top();
        q.pop();
        if(!viz[da.a])
        {
            viz[da.a]=1;
            poz=start[da.a];
            while(poz)
            {
                vecin=t[0][poz];
                if(v[vecin]>v[da.a]+cost[poz])
                {
                    v[vecin]=v[da.a]+cost[poz];
                    q.push({vecin,v[vecin]});
                }
                poz=t[1][poz];
            }
        }

    }
}
int main()
{
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    int m,x,y,k=0;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&cost[++k]);
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
    for(int i=1;i<=n;++i)
        v[i]=1999999999;
    v[1]=0;
    d(1);
    for(int i=2;i<=n;++i)
    {
        if(v[i]==1999999999)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",v[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}