using namespace std;
#include<cstdio>
#include<vector>
#include<algorithm>
#define Nm (1<<16)
#define Inf (1<<30)
#define f first
#define s second
int Dm[Nm],H[Nm],P[Nm],n,h;
vector< pair<int,int> > G[Nm];

void read()
{
    int m,a,b,c;

    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back(make_pair(b,c));
    }
}

void sink(int x)
{
    int v=H[x],son=x<<1;

    while(son<=h)
    {
        if(son<h && Dm[H[son|1]]<Dm[H[son]])
            son|=1;
        if(Dm[v]<=Dm[H[son]])
            break;
        H[x]=H[son]; P[H[x]]=x;
        x=son; son<<=1;
    }
    H[x]=v; P[v]=x;
}

void lift(int x)
{
    int v=H[x];

    while(x>1 && Dm[v]<Dm[H[x>>1]])
    {
        H[x]=H[x>>1];
        P[H[x]]=x;
        x>>=1;
    }
    H[x]=v; P[v]=x;
}

void solve()
{
    int i,x;
    vector< pair<int,int> >::iterator it;

    H[h=1]=1; P[1]=1;
    for(i=2;i<=n;++i)
    {
        Dm[i]=Inf;
        H[++h]=i;
        P[i]=h;
    }

    while(h)
    {
        x=H[1];
        if(Dm[x]==Inf)
            break;
        H[1]=H[h--];
        sink(1);

        for(it=G[x].begin();it!=G[x].end();++it)
            if(Dm[x]+it->s<Dm[it->f])
            {
                Dm[it->f]=Dm[x]+it->s;
                lift(P[it->f]);
            }
    }
}

void write()
{
    int i;

    freopen("dijkstra.out","w",stdout);
    for(i=2;i<n;++i)
        printf("%d ",Dm[i]<Inf?Dm[i]:0);
    printf("%d\n",Dm[i]<Inf?Dm[i]:0);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}