#include <iostream>
#include <vector>

struct edge {
    int src;
    int dst;
    int weight;
};

struct vertex {
    vertex() { visited = false; cost = MAX; }
    static const int MAX = std::numeric_limits<int>::max();

    void add_edge(int src, int dst, int weight) {
        edge e {src, dst, weight };
        edges.push_back(e);
    }

    std::vector<edge> edges;
    int cost;
    bool visited;
};

int next_vertex_to_visit(const std::vector<vertex>& verts) {
    //find next vertex to visit for calculations, so that is a vertex
    //that has not been visited before and has the lowest cost;
    int cost = vertex::MAX;
    int vert_idx = -1;
    for (int i=0; i<verts.size(); i++) {
        if (verts[i].visited == false && verts[i].cost < cost) {
            cost = verts[i].cost;
            vert_idx = i;
        }
    }
    return vert_idx;
}

void calculate_costs(std::vector<vertex>& verts) {
    if (verts.size() == 0)
        return;
    verts[0].cost = 0;  //source vertex has cost of zero

    for (int n=0; n<verts.size(); n++) {
        int idx = next_vertex_to_visit(verts);
        for (int i=0; i<verts[idx].edges.size(); i++) {
            int cost = verts[idx].cost + verts[idx].edges[i].weight;
            int dst = verts[idx].edges[i].dst;
            if (cost < verts[dst].cost)
                verts[dst].cost = cost;
        }
        verts[idx].visited = true;
    }
}

void print_costs(std::vector<vertex>& verts) {
    for (auto v : verts) {
        std::cout << v.cost << " ";
    }
    std::cout << std::endl;
}

std::vector<vertex> create_graph() {
    std::vector<vertex> verts;

    {   vertex v;
        v.add_edge(0, 1, 4);
        v.add_edge(0, 5, 2);
        verts.push_back(v);
    }
    {   vertex v;
        v.add_edge(1, 2, 5);
        v.add_edge(1, 3, 6);
        verts.push_back(v);
    }
    {   vertex v;
        v.add_edge(2, 1, 3);
        verts.push_back(v);
    }
    {   vertex v;
        v.add_edge(3, 2, 1);
        verts.push_back(v);
    }
    {   vertex v;
        v.add_edge(4, 1, 1);
        v.add_edge(4, 3, 3);
        verts.push_back(v);
    }
    {   vertex v;
        v.add_edge(5, 4, 1);
        verts.push_back(v);
    }

    return verts;
}

int main() {
    auto verts = create_graph();
    calculate_costs(verts);
    print_costs(verts);

    return 0;
}