#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct noduri
{
    int nod,c;
}aux;
vector<noduri>v[50010];
vector<noduri>::iterator it;
int sol[50010],n,m,i,x,y,c;
char vaz[50010];

struct inheap
{
    int x;
    bool operator <(const inheap &aux) const
    {
        return sol[x]>sol[aux.x];
    }
}auxh;
priority_queue<inheap>heap;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        aux.nod=y;
        aux.c=c;
        v[x].push_back(aux);
    }
    memset(sol,-1,sizeof sol);
    sol[1]=0;
    auxh.x=1;
    heap.push(auxh);
    while(!heap.empty())
    {
        auxh=heap.top();
        heap.pop();
        x=auxh.x;
        if(vaz[x]) continue;
        vaz[x]=1;
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            aux=*it;
            if(!vaz[aux.nod])
                if(sol[aux.nod]>sol[x]+aux.c || sol[aux.nod]==-1)
                {
                    sol[aux.nod]=sol[x]+aux.c;
                    auxh.x=aux.nod;
                    heap.push(auxh);
                }
        }
    }
    for(i=2;i<=n;i++)
        if(sol[i]==-1) printf("0 ");
        else printf("%d ",sol[i]);
    return 0;
}