#include<fstream>
#include<vector>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int maxn=50005;
const int INF=0x3f3f3f3f;

struct nod
{
    int w;
    int dis;
}one;

vector<nod>a[maxn];

int dis[maxn],pos[maxn],i,j,n,x,y,z,m,h[maxn],k;

void push(int x)
{
    int aux;
    while(x>1&&dis[h[x]]<dis[h[x>>1]])
    {
        aux=h[x];
        h[x]=h[x>>1];
        h[x>>1]=aux;
        pos[h[x]]=x;
        pos[h[x>>1]]=x>>1;
        x>>=1;
    }
}

void pop(int x)
{
    int y=0,aux;
    while(x!=y)
    {
        y=x;
        if((y<<1)<=k&&dis[h[y<<1]]<dis[h[x]])
            x=y<<1;
        if((y<<1)+1<=k&&dis[h[(y<<1)+1]]<=dis[h[x]])
            x=(y<<1)+1;
        aux=h[x];
        h[x]=h[y];
        h[y]=aux;
        pos[h[x]]=x;
        pos[h[y]]=y;
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        one.w=y;
        one.dis=z;
        a[x].push_back(one);
    }

    pos[1]=1;
    h[1]=1;
    dis[1]=0;
    for(i=2;i<=n;++i)
        dis[i]=INF,pos[i]=-1;

    k=1;
    while(k)
    {
        x=h[1];
        h[1]=h[k--];
        pos[h[1]]=1;
        h[k+1]=0;
        pop(1);
        for(vector<nod>::iterator it=a[x].begin();it!=a[x].end();++it)
            if(dis[it->w]>dis[x]+it->dis)
            {
                dis[it->w]=dis[x]+it->dis;
                if(pos[it->w]!=-1)
                    push(pos[it->w]);
                else
                {
                    h[++k]=it->w;
                    pos[h[k]]=k;
                    push(k);
                }
            }
    }

    for(i=2;i<=n;++i)
        g<<(dis[i]<INF?dis[i]:0)<<" ";
    g<<"\n";
    f.close();
    g.close();

    return 0;
}