#include<cstdio>
#include<map>
#include<set>
int n,m;
long long path[100042]={1};
struct __{
	int node;
	__(int asdf){node=asdf;}
};
inline bool operator<(const __ &A,const __ &B)
{
	return path[A.node]<path[B.node];
}
std::map<int,std::map<int,long long> > edges;
std::set<__> seto;
inline void add(int a,int b,long long c)
{
	if(a==b)return;
	std::map<int,std::map<int,long long> >::iterator miii=edges.find(a);
	if(miii==edges.end())
	{
		edges[a][b]=c;
		return;
	}
	std::map<int,long long>::iterator mii=miii->second.find(b);
	if(mii==miii->second.end())
	{
		miii->second[b]=c;
		return;
	}
	if(mii->second>c)
		mii->second=c;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		if(i>10000)return 0;
		int k,a,b;
		long long c;
		scanf("%d%d%d%lld",&k,&a,&b,&c);
		--a;--b;
		if(k==1)add(a,b,c);
		else
		{
			std::map<int,std::map<int,long long> >::iterator miii=edges.find(a);
			if(miii==edges.end())continue;
			for(std::map<int,long long>::iterator mii=miii->second.begin();mii!=miii->second.end();++mii)
				add(b,mii->first,mii->second+c);
		}
	}

//	for(std::map<int,std::map<int,int> >::iterator miii=edges.begin();miii!=edges.end();++miii)
//		for(std::map<int,int>::iterator mii=miii->second.begin();mii!=miii->second.end();++mii)
//			printf("%d %d  %d\n",miii->first,mii->first,mii->second);
	
	seto.insert(__(0));
	while(!seto.empty())
	{
		std::set<__>::iterator it=seto.begin();
		int x=it->node;
		seto.erase(it);
		std::map<int,std::map<int,long long> >::iterator miii=edges.find(x);
		if(miii==edges.end())continue;
		for(std::map<int,long long>::iterator mii=miii->second.begin();mii!=miii->second.end();++mii)
		{
			if(!path[mii->first]||path[mii->first]>path[x]+mii->second)
			{
				path[mii->first]=path[x]+mii->second;
				seto.insert(mii->first);
			}
		}
	}
	for(int i=1;i<n;++i)
		printf("%lld\n",path[i]-1);
	return 0;
}
