#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,c[500005],dist[50005],ok[50005];
#define nrmare 250000005
struct nod
{
    int inf;
    int d;
    nod *adr;
} *v[50005];
void creare()
{
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        nod *p=new nod;
        p->inf=y;
        p->d=z;
        p->adr=v[x];
        v[x]=p;
    }
}
void bfs(int x)
{
    int pr,ul;
    pr=ul=1;
    c[pr]=x;ok[x]=1;
    while(pr<=ul)
    {
        x=c[pr++];
        for(nod *p=v[x];p!=NULL;p=p->adr)
        {
            if(dist[x]+p->d<dist[p->inf])
            {
                dist[p->inf]=dist[x]+p->d;
                if(ok[p->inf]==0)
                {
                    ok[p->inf]=1;
                    c[++ul]=p->inf;
                }
            }
        }
        ok[x]=0;
    }
}
int main()
{
    f>>n>>m;
    creare();
    for(int i=2;i<=n;i++)
        dist[i]=nrmare;
    bfs(1);
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==nrmare)
            g<<0<<' ';
        else
            g<<dist[i]<<' ';
    }
    return 0;
}