#include <cstdio>
#include <set>
#include <algorithm>


#define MAXN 50002
#define inf 1<<30
#define FOR(i,a,b) for(i=a;i<=b;i++)

using namespace std;


struct graf
{
    int nod,cost;
    graf *next;
};

graf *a[MAXN];
int d[MAXN],n,m,k;
multiset<int> h;
multiset<int> :: iterator it;


inline void read()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i;
    FOR(i,1,m)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        graf *q=new graf;
		q->nod=y;
		q->cost=z;
		q->next=a[x];
		a[x]=q;
    }
}

inline void dijkstra()
{
    int i;
    FOR(i,1,n)
        d[i]=inf;
    d[1]=0;
    h.insert(1);
    while(!h.empty())
    {
        it=h.begin();
        int min=*it;
        h.erase(it);
        graf *q=a[min];
        while(q)
        {
            if(d[q->nod]>d[min]+q->cost)
            {
                d[q->nod]=d[min]+q->cost;
                if(h.find(q->nod)==h.end())
                    h.insert(q->nod);
            }
            q=q->next;
        }
    }
}

void print()
{
    for(it=h.begin();it!=h.end();it++)
        printf("%d ",*it);
}


int main()
{
    read();
    dijkstra();
    for(int i=2;i<=n;i++)
	{
		if(d[i]==inf)
			printf("0 ");
		else
			printf("%d ",d[i]);
	}
	printf("\n");
    return 0;
}