# 打扣

#include <bits/stdc++.h>
using namespace std;

const int Row = 500;
const int Col = 500;
const int Floor = 100;
class point_dat //for display purposes
{
    private:
        int x,y,z;
        // ex. x*Col*Floor + y*Floor + Floor
        //bool stair;
    public:
        //bool is_stair(int temp_id){ return point[temp_id].stair;} 
}point[Row*Col*Floor];
vector<pair<int, int> > edge[Row*Col*Floor]; // first = go to  second = weight

vector<int> dijisktra(int start, int target)
{
    edge[0].push_back({1,1});
    edge[1].push_back({0,1});
    edge[1].push_back({2,1});
    edge[2].push_back({1,1});
    edge[2].push_back({3,1});
    edge[3].push_back({2,1});
    edge[3].push_back({4,1});
    edge[4].push_back({3,1});
    edge[4].push_back({5,1});
    edge[5].push_back({4,1});
    edge[5].push_back({6,1});
    edge[6].push_back({5,1});
    edge[6].push_back({7,1});
    edge[7].push_back({6,1});
    edge[7].push_back({8,1});
    edge[8].push_back({7,1});
    edge[8].push_back({9,1});
    edge[9].push_back({8,1});
    edge[9].push_back({10,1});
    edge[10].push_back({9,1});
    edge[10].push_back({11,1});
    edge[11].push_back({10,1});
    edge[11].push_back({12,1});
    edge[12].push_back({11,1});
    edge[12].push_back({13,1});
    edge[13].push_back({12,1});
    edge[13].push_back({15,1});
    edge[15].push_back({13,1});
    edge[15].push_back({16,1});
    edge[16].push_back({15,1});
    edge[16].push_back({17,1});
    edge[17].push_back({16,1});
    edge[17].push_back({18,1});
    edge[18].push_back({17,1});
    edge[18].push_back({19,1});
    edge[19].push_back({18,1});
    edge[20].push_back({21,1});
    edge[21].push_back({20,1});
    edge[23].push_back({24,1});
    edge[24].push_back({23,1});
    edge[25].push_back({26,1});
    edge[26].push_back({25,1});
    edge[26].push_back({27,1});
    edge[27].push_back({26,1});
    edge[27].push_back({28,1});
    edge[28].push_back({27,1});
    edge[28].push_back({29,1});
    edge[29].push_back({28,1});
    edge[29].push_back({30,1});
    edge[30].push_back({29,1});
    edge[30].push_back({31,1});
    edge[31].push_back({30,1});
    edge[31].push_back({32,1});
    edge[32].push_back({31,1});
    edge[32].push_back({33,1});
    edge[33].push_back({32,1});
    edge[33].push_back({34,1});
    edge[34].push_back({33,1});
    edge[34].push_back({35,1});
    edge[35].push_back({34,1});
    edge[35].push_back({36,1});
    edge[36].push_back({35,1});
    edge[36].push_back({37,1});
    edge[37].push_back({36,1});
    edge[37].push_back({38,1});
    edge[38].push_back({37,1});
    edge[38].push_back({39,1});
    edge[39].push_back({38,1});
    edge[22].push_back({39,1});
    edge[39].push_back({22,1});

    int n = Row*Col*Floor;
    int dist[n+5];
    int from[n+5];
    priority_queue<pair<int, int> ,vector<pair<int, int> >,greater<pair<int, int> >> pq;
    
    for(int i=1; i<=n; i++) if(i != start) dist[i]=1e9;
    from[start] = -1;
	pq.push({0,start});
    
	while(!pq.empty())
	{
		pair<int, int> u=pq.top();
		pq.pop();
		for(pair<int, int> v : edge[u.first])
            if(dist[v.first] > dist[u.second] + v.second)
            {
                dist[v.first] = dist[u.second] + v.second;
                from[v.first] = u.second;
                pq.push({dist[v.first],v.first});
            }
	}
    
    vector<int> route;
    for(int i=target; i!=-1; i=from[i])
        route.push_back(i);
    reverse(route.begin(),route.end());
    return route;
}

// 到這裡就好


void build_Graph()
{
    FILE *fp;
    fp = freopen("data.txt","r",stdin);
    // input format: from to weight
    int from,to,weight;
    while(cin >> from)
    {
        cin >> to >> weight;
        edge[from].push_back({to,weight});
        edge[to].push_back({from,weight});
    }
    fclose(fp);
}

map<string, int> point_id_query;//some kind of database
int point_id(string ap_id)
{
    return point_id_query[ap_id];
}
int user_at(string user_id)
{
    string ap_id = //use user_id to get ap_id
    return point_id(ap_id);
}

int user_to(string user_id)
{
    int temp = //find out where user wants to go
    return temp;
}

void route_display(string user_id)
{
    int at = user_at(user_id);
    int to = user_to(user_id);
    vector<int>route = dijisktra(at, to);
    //display
    for(int v:route)//example
    {
        draw_red(point[v].x,point[v].y,point[v].z);
    }
}