#include <cstdio>
#include <queue>

using namespace std;

const int inf=2000000000;

struct edge
{
    int nod,c;
    edge(int nod1,int c1) {nod=nod1;c=c1;}
};

struct heap
{
    int nod,c;
    heap(int nod1,int c1) {nod=nod1;c=c1;}
    bool operator <(const heap &aux) const
    {
        return c>aux.c;
    }
};

priority_queue<heap> h;
vector<edge> v[50010];
int d[50010];


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int x,y,c,n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(edge(y,c));
    }
    d[1]=0;
    for(int i=2;i<=n;i++) d[i]=inf;
    h.push(heap(1,0));
    while(!h.empty())
    {
        heap a=h.top();
        h.pop();
        if(d[a.nod]!=a.c) continue;
        int nod=a.nod;
        for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            if(d[it->nod]>d[nod]+it->c)
        {
            d[it->nod]=d[nod]+it->c;
            h.push(heap(it->nod,d[it->nod]));
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]==inf) printf("0");
        else printf("%d ",d[i]);
    return 0;
}