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

using namespace std;

int sol[50010],n,m,i,x,y,c;
char vaz[50010];
struct xuri
{
    int x,c;
    bool operator <(const xuri &aux) const
    {
        return c>aux.c;
    }
}aux;
vector<xuri>v[50010];
vector<xuri>::iterator it;
priority_queue<xuri>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.x=y;
        aux.c=c;
        v[x].push_back(aux);
    }
    memset(sol,-1,sizeof sol);
    sol[1]=0;
    aux.x=1;
    aux.c=0;
    heap.push(aux);
    while(!heap.empty())
    {
        aux=heap.top();
        heap.pop();
        if(aux.c>sol[aux.x]) continue;
        x=aux.x;
        vaz[x]=1;
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            aux=*it;
            if(!vaz[aux.x])
                if(sol[aux.x]>sol[x]+aux.c || sol[aux.x]==-1)
                {
                    sol[aux.x]=sol[x]+aux.c;
                    aux.c=sol[aux.x];
                    heap.push(aux);
                }
        }
    }
    for(i=2;i<=n;i++)
        if(sol[i]==-1) printf("0 ");
        else printf("%d ",sol[i]);
    return 0;
}