#include<stdio.h>
#include<deque>
#include<vector>
using namespace std;

const int N=50001,M=1000002,INF=1000000000;

int s[N],n,m,q[M],f=1,l=1,c[N];

struct xy{
	int to,c;
};

vector <xy> v[N];

void read()
{
	int x;
	xy rd;
	fscanf("%d%d",&n,&m,IN);
	for( int i=1 ; i<=m ; ++i )
	{
		fscanf("%d%d%d",&x,&rd.to,&rd.c,IN);
		v[x].push_back(rd);
		++s[x];
	}
}

void act()
{
	for( int i=2 ; i<=n ; ++i )
		c[i]=INF;
}

void use( int x )
{
	for( int i=0 ; i<s[x] ; ++i )
		if( c[ v[x][i].to ] > c[x] + v[x][i].c )
		{
			c[ v[x][i].to ] = c[x] + v[x][i].c;
			q[++l]=v[x][i].to;
		}
}

void bf()
{
	q[1]=1;
	while(f<=l)
	{
		use(q[f]);
		++f;
	}
}

void afis()
{
	for( int i=2 ; i<=n ; ++i )
		if(c[i]==INF)
			fprintf("0 ",OUT);
		else
			fprintf("%d ",c[i],OUT);
}

int main()
{
	IN=fopen("dijkstra.in","r");
	OUT=fopen("dijkstra.out","w");
	read();
	act();
	bf();
	afis();
	return 0;
}