#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
FILE*in=fopen("dijkstra.in","r");
FILE*out=fopen("dijkstra.out","w");
struct nod
{
    int nod,cost;
};
nod a;
int N,M,A,B,C,i,c,n;
int d[50003];
bool pqi[50003];
vector<nod> v[50003];
struct use
{
    int x,useless;
};
use k;
priority_queue<use> pq;
inline bool operator<(use a,use b)
{
    return d[a.x]>d[b.x];
}
void dijkstra()
{
    d[1]=0;
    pqi[1]=1;
    for(i=2;i<=N;i++)
    {
        d[i]=2000000000;
    }
    k.x=1;
    pq.push(k);
    while(!pq.empty())
    {
        int acn=pq.top().x;
        pq.pop();
        pqi[acn]=0;
        for(int j=0;j<v[acn].size();j++)
        {
            n=v[acn][j].nod;
            c=v[acn][j].cost;
            if(c+d[acn]<d[n])
            {
                d[n]=c+d[acn];
                if(pqi[n]==0)
                {
                    pqi[n]=1;
                    k.x=n;
                    pq.push(k);
                }
            }
        }
    }
}
int main()
{
    fscanf(in,"%d%d",&N,&M);
    for(i=1;i<=M;i++)
    {
        fscanf(in,"%d%d%d",&A,&B,&C);
        a.nod=B;
        a.cost=C;
        v[A].push_back(a);
    }
    dijkstra();
    for(i=2;i<=N;i++)
    {
        fprintf(out,"%d ",d[i]);
    }
}