#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define maxim 2147483645;
struct nod
{
    int cost,val;
    nod *urm;
};
typedef nod *pnod;
bool viz[50003];
pnod v[50003],p;
int n;
long long dist[50003];
void ad(int x,int y,int z)
{
    p=new nod;
    p->cost=z;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int distmin()
{
    int mini,min_index,i;
    mini=maxim;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0 and dist[i]<=mini)
        {
            mini=dist[i];
            min_index=i;
        }
    }
    return min_index;
}
int main()
{
    int x,y,z,i,m;
    f>>n>>m;
    for(i=1;i<=n+1;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=maxim;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        ad(x,y,z);
    }
    dist[1]=0;
    for(i=2;i<=n;i++)
    {
        x=distmin();
        viz[x]=1;
        p=v[x]->urm;
        while(p)
        {
            if( dist[x]+p->cost<=dist[p->val])
            {
                dist[p->val]=dist[x]+p->cost;
            }
            p=p->urm;
        }
    }
    for(i=2;i<=n;i++)
        if(dist[i]==2147483645)
            dist[i]=0;
    for(i=2;i<=n;i++)
        g<<dist[i]<<" ";
    f.close();
    g.close();
    return 0;
}