define _CRT_SECURE_NO_WARNI NGS include iostream include queue include

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;


int parnt[] = { -1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3 };
int level[13] = { 0 };


int getLevel(int cur)
{
	if (level[cur] != -1)
		return level[cur];
	if (parnt[cur] == -1)
	{
		level[cur] = 1;
		return 1;
	}
	level[cur] = getLevel(parnt[cur]) + 1;
	return level[cur];
}


struct edge
{
	int a, b, cost;
	edge(int a = 0, int b = 0, int cost = 0) :a(a), b(b), cost(cost){};
};



edge arr[13];

struct node
{
    int value;
    node* next;
    node(int vl):value(vl){};
};

class stack
{
        node* head;
      
public: 
    stack()
    {
        head = 0;
    }
    int top()
    {
        if (head == 0)
            return -999999999;
        return head->value;
    }
    bool isEmpty()
    {
        return head == 0;    
    }
    void push(int vl)
    {
        node* newElem = new node(vl);
        newElem->next = head;
        head = newElem;
    }
    void pop()
    {
        if (head == 0)
            return;
        node* tmp = head;
        head = head->next;
        delete tmp;
    }      

    void deleteNodeByVal(int vl)
    {
        node* cNode = head;
        while (cNode != 0)
        {
            if (cNode->value == vl)
            {
                node* tmp = cNode;
                cNode = cNode->next;
                delete tmp;
                continue;
            }
            else
            {
                cNode = cNode->next;
            }
        }
    }

};



class PuchkiDug
{
private:

	int* heads;
	int* links;
	edge* edges_p;

	int n;
	int m;

public:
	PuchkiDug(edge* allEdges, int n, int m) : n(n), m(m)
	{
		edges_p = allEdges;
		heads = new int[n];
		links = new int[m];
		
		memset(heads, -1, sizeof(int) * n);
		memset(links, -1, sizeof(int) * m);

		for (int i = 0; i < m; ++i)
		{
			links[i] = heads[edges_p[i].a];
			heads[edges_p[i].a] = i;
		}
	}

	void printData()
	{
		for (int i = 0; i < n; ++i)
		{
			int cr = heads[i];			
			while (cr != -1)
			{
				cout << edges_p[cr].b << " ";
				cr = links[cr];
			}
			cout << endl;
		}	
	}

	void getParentTree(int* outp, int start)	
	{
		memset(outp, -1, sizeof(int)* n);


		queue<int> que;
		que.push(start);
		outp[start] = -2;
		while (!que.empty())
		{
			int cr = que.front();
			que.pop();

			int hd = heads[cr];

			while (hd != -1)
			{
				int to = edges_p[hd].b;
				if (outp[to] == -1)
				{
					outp[to] = cr;
					que.push(to);
				}
				hd = links[hd];
			}
		}
	}


    void djicstra(int* distances, edge* edges, int vCount, int eCount, int start)
    {
        int maxEdge = 0;
        for (int i = 0; i < eCount; ++i)
        {
            maxEdge = max(maxEdge, edges[i].cost);
        }

        stack* cherpack = new stack[maxEdge];
        distances[start] = 0;
        bool isWorking = true;
        cherpack[0].push(start);
        while (isWorking)
        {
            isWorking = false;
            for (int i = 0; i < maxEdge; ++i)
            {
                if (cherpack[i].isEmpty())
                    continue;
                
                int cVert = cherpack[i].top();
                cherpack[i].pop();
                int dist = distances[cVert];

                int cEdge = heads[cVert];
                while (cEdge != -1)
                {
                    int nx = edges[cEdge].b;
                    int cost = edges[cEdge].cost;
                    if (distances[nx] > distances[cVert] + cost)
                    {
                        int cherp = distances[nx] % maxEdge;
                        distances[nx] = distances[cVert] + cost;
                        cherpack[cherp].deleteNodeByVal(nx);
                        cherp = distances[nx] % maxEdge;
                        cherpack[cherp].push(nx);
                        isWorking = true;
                    }
                    cEdge = links[cEdge];
                }


            }
        
        }
    
    
    }

};






int main()
{
	memset(level, -1, sizeof(int) * 13);
	arr[0] = edge(0, 1, 2);
	arr[1] = edge(0, 2, 4);
	arr[2] = edge(0, 3, 1);

	arr[3] = edge(1, 4, 20);
	arr[4] = edge(1, 5, 30);
	arr[5] = edge(1, 6, 13);

	arr[6] = edge(2, 7, 12);
	arr[7] = edge(2, 8, 23);
	arr[8] = edge(2, 9, 41);

	arr[9] = edge(3, 10, 51);
	arr[10] = edge(3, 11, 53);
	arr[11] = edge(3, 12, 93);
	arr[12] = edge(3, 0, 85);

	PuchkiDug puch(arr, 13, 13);

    int dstts[13] = {0};
    for (int i = 0; i < 13; ++i)
        dstts[i] = 999999999;

    puch.djicstra(dstts, arr, 13, 13, 3);

    for (int i = 0; i < 13; ++i)
    {
        cout << dstts[i] << " ";
    }

}