#include <cstdio>
#include <queue>
#include <vector>
#define oo 2147483647
using namespace std;
struct nod
{
    int x,c;
    bool operator <(const nod &A) const
    {
        return c>A.c ;
    }
};

priority_queue <nod> q;
vector <nod> a[50003];
int sol[50003];
int n,m;
void R()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,z;
    nod r;
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&z,&r.x,&r.c);
        a[z].push_back(r);
    }
}
void Dijkstra()
{
    int i;
    nod r,nr;
    for(i=2; i<=n; i++)
        sol[i]=oo;

    r.x=1; r.c=0;
    q.push(r);
    vector <nod>::iterator it;
    while(!q.empty())
    {
        r=q.top();
        q.pop();
        for(it=a[r.x].begin(); it!=a[r.x].end(); it++)
        {
            nr=*it;
            if(sol[nr.x] > sol[r.x]+nr.c)
            {
                sol[nr.x]=sol[r.x]+nr.c;
                q.push(nr);
            }
        }
    }

    for(i=2; i<=n; i++)
        if(sol[i]==oo)
        printf("0 ");
    else
        printf("%d ",sol[i]);
}
int main()
{
    R();
    Dijkstra();
    return 0;
}