#include <fstream>
#define pinf 1<<30
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod{
            int info,c;
            nod *next;
            }*l[50001],*p;
int i,j,n,cost,x,y,d[50001],viz[50001],pr,u,co[250001],m;
void dijkstra(int start )
{
    pr=1;
    u=1;
    for(i=1;i<=n;++i)
        d[i]=pinf;
    d[start]=0;
    viz[start]=1;
    co[u]=start;
    while(pr<=u)
    {
        x=co[pr];
        p=new nod;
        p=l[co[pr++]];
        while(p)
        {
            if(d[x]+p->c<d[p->info])
                {
                    d[p->info]=d[x]+p->c;
                    co[++u]=p->info;
                }
            p=p->next;
        }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
        {
            fin>>x>>y>>cost;
            p=new nod;
            p->info=y;
            p->c=cost;
            p->next=l[x];
            l[x]=p;
        }
    dijkstra(1);
    for(i=2;i<=n;++i)
            fout<<d[i]<<" ";
    return 0;
}