#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
#define dim 8192

using namespace std;

int i,n,m,dist[50010],pz;
char c[dim+16];

struct nod
{
    int x,d;
};

vector<nod>a[50010];
queue<int> q;
bitset<50010> fol;

inline void cit(int &x)
{
    x=0;
    while(c[pz]<'0'||c[pz]>'9')
    if(++pz==dim) fread(c,1,dim,stdin),pz=0;

    while(c[pz]>='0'&&c[pz]<='9')
    {
        x=x*10+c[pz]-'0';
        if(++pz==dim) fread(c,1,dim,stdin),pz=0;
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    cit(n);
    cit(m);

    for(i=1;i<=m;++i)
    {
        int x,y,d;
        nod aux;

        cit(x);cit(y);cit(d);
        aux.x=y;
        aux.d=d;
        a[x].push_back(aux);
    }

    fol[1]=1;
    q.push(1);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        fol[u]=0;

        for(i=0;i<a[u].size();++i)
            if(dist[u]+a[u][i].d<dist[ a[u][i].x]||dist[ a[u][i].x]==0)
            {
                dist[ a[u][i].x ]=dist[u]+a[u][i].d;
                if(!fol[ a[u][i].x ])
                {
                    q.push(a[u][i].x);
                    fol[a[u][i].x]=1;
                }
            }
    }

    for(i=2;i<=n;++i) printf("%d ",dist[i]);

    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}