#include<bits/stdc++.h>
#define INF numeric_limits<int>::max()
#define ERROR -1
using namespace std;
struct node{
	string value;
	vector<pair<int,double> > edge;
	node(){}
	node(string _value){
		value = _value;
	}
};
vector<node> graph;
int find(const vector<node>& graph,string value){
	int len = graph.size();
	for(int i = 0;i < len;i ++){
		if(graph[i].value == value) return i;
	}
	return ERROR;
}
void addnode(vector<node>* graph,string value){
	node newnode(value);
	graph->push_back(newnode);
}
void addedge(vector<node>* graph,string value1,string value2,double weight = 1.0){
	int index1 = find(*graph,value1);
	int index2 = find(*graph,value2);
	if(index1 == ERROR || index2 == ERROR){
//		cout<<"could not find value."<<endl;
		return;
	}
	graph->at(index1).edge.push_back({index2,weight});
}

void dfs(const vector<node>& graph,set<int>& visited,int start = 0){
	if(visited.count(start) > 0){
		return;
	}
	cout<<graph[start].value<<' ';
	visited.insert(start);
	for(auto it : graph[start].edge){
		dfs(graph,visited,it.first);
	}
}

vector<double> dijkstra(const vector<node>& g,int start = 0){
	vector<node> graph(g);
	vector<pair<double,bool> > pres(graph.size(),{INF,false});
	bool con = true;
	int len = pres.size();
	pres[start].first = 0;
	while(con){
		double minl = pres[0].first;
		int minn = 0;
		for(int i = 0;i < len;i ++){
			if(minl > pres[i].first && !pres[i].second){
				minl = pres[i].first;
				minn = i;
			}
			//cout<<3<<endl;
		}
		pres[minn].second = true;//永久标注
		for(auto it : graph[minn].edge){
			//cout<<pres[it.first].first<<endl;
			auto tmpv = min(pres[it.first].first,pres[minn].first + it.second);
			pres[it.first].first = tmpv;
			//cout<<"ok" << pres[it.first].first<< " " << tmpv << endl;
			//cout<<2<<endl;
		}
		con = false;
		for(auto it : pres){
			//cout<<it.second<<endl;
			if(!it.second){
				con = true;
				break;
			}
		}
		//cout<<1<<endl;
	}
	vector<double> res;
	for(auto it : pres){
		//cout<<"inner" <<it.first<<endl;
		res.push_back(it.first);
	}
	return res;
}
int main(){
	addnode(&graph,"0");
	addnode(&graph,"1");
	addnode(&graph,"2");
	addnode(&graph,"3");
	addnode(&graph,"4");
	addnode(&graph,"5");
	addnode(&graph,"6");
	addnode(&graph,"7");
	addnode(&graph,"8");
	addnode(&graph,"9");
	addedge(&graph,"0","1",5);
	addedge(&graph,"0","6",6);
	addedge(&graph,"1","2",7);
	addedge(&graph,"1","6",9);
	addedge(&graph,"2","3",4);
	addedge(&graph,"2","4",8);
	addedge(&graph,"2","6",1);
	addedge(&graph,"3","5",4);
	addedge(&graph,"4","5",6);
	addedge(&graph,"4","9",3);
	addedge(&graph,"5","8",2);
	addedge(&graph,"6","9",2);
	addedge(&graph,"7","4",2);
	addedge(&graph,"7","8",4);
	addedge(&graph,"8","4",1);
	addedge(&graph,"9","7",3);
	addedge(&graph,"9","8",9);
//	set<int> visited;
//	dfs(graph,visited);
//	cout<<endl;
	vector<double> res(dijkstra(graph));
	for(auto it : res){
		cout<<it<<endl;
	}
}