#include<cstdio>
#include<vector>
#include<queue>
#define N 50005
using namespace std;
int n,m,cost[N];
bool v[N];


typedef struct{int nod; int ct;} pct;

bool operator<(pct x, pct y)
	{
		return x.ct>y.ct;
	}

const int maxx=1<<30;

priority_queue< pct > q;
vector< int > a[N];
vector< int > c[N];
void citire()
{
	int i,x,y,z;
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=0;i<m;++i){
        scanf("%d %d %d",&x,&y,&z);
        a[x].push_back(y);
        c[x].push_back(z);
    }
}
void dj()
{
    pct t,t1;
    int x,y,i;
    for(i=1;i<=n;++i)
		cost[i]=maxx;
    t.nod=1;
    t.ct=0;
    cost[1]=0;
    q.push(t);
    while(!q.empty()){
        t=q.top();
        q.pop();
        if(!v[t.nod]){
			x=t.nod;
			//v[x]=1; 
			for(i=0;i<a[x].size();++i)
				if(v[a[x][i]]==0 && t.ct+c[x][i]<cost[a[x][i]])
                {
					cost[a[x][i]]=t.ct+c[x][i];
					t1.nod=a[x][i]; t1.ct=cost[t1.nod];
					q.push(t1);
                }
        }
    }
}


int main()
{
	citire();
    dj();
    for(int i=1;i<=n;++i)
		if(cost[i]==maxx) cost[i]=0;
    for(int i=2;i<=n;++i)
		printf("%d ",cost[i]);
	//printf("\n%lf\n",(double)clock()/CLOCKS_PER_SEC);
}