C++17

#include <iostream>
#include <vector>
#include <set>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <iterator>
using namespace std;

class Node
{
    friend bool operator< (const Node &, const Node &);
private:
    int v, w;
public:
    Node();
    Node(int v, int w);
    int getV() const;
    int getW() const;
};

class Distance
{
    friend bool operator> (const Distance &, const Distance &);
private:
    int to, dis;
public:
    Distance();
    Distance(int to, int dis);
    int getTo() const;
    int getDis() const;
};

class Graph
{
    vector<multiset<Node>> g;
public:
    Graph();
    Graph(int n);
    void resize(int);
    int size();
    void insert(int, int, int);
    vector<int> *dijkstra(int);
    static int inf();
};

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    Graph g(m);
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g.insert(u, v, w);
    }
    auto mindis = g.dijkstra(s);
    copy(mindis->begin()+1, mindis->end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    delete mindis;
    return EXIT_SUCCESS;
}

Node::Node()
{
    v = w = 0;
}

Node::Node(int v, int w)
{
    this->v = v;
    this->w = w;
}

int Node::getV() const
{
    return v;
}

int Node::getW() const
{
    return w;
}

Distance::Distance()
{
    to = dis = 0;
}

Distance::Distance(int to, int dis)
{
    this->to = to;
    this->dis = dis;
}

int Distance::getTo() const
{
    return to;
}

int Distance::getDis() const
{
    return dis;
}

Graph::Graph() {}

Graph::Graph(int n)
{
    resize(n);
}

void Graph::resize(int n)
{
    g.resize(n+1);
}

int Graph::size()
{
    return g.size() - 1;
}

void Graph::insert(int u, int v, int w)
{
    g[u].insert(Node(v, w));
}

vector<int> *Graph::dijkstra(int s)
{
    priority_queue<Distance, vector<Distance>, greater<Distance>> pq;
    pq.push(Distance(s, 0));
    vector<bool> vis(size());
    auto mindis = new vector<int>(size()-1);
    fill(mindis->begin(), mindis->end(), inf());
    while(!pq.empty())
    {
        Distance h = pq.top();
        pq.pop();
        int u = h.getTo(), dis = h.getDis();
        if(vis[u])
        {
            continue;
        }
        (*mindis)[u] = dis;
        vis[u] = true;
        for(auto it : g[u])
        {
            int v = it.getV(), w = it.getW();
            if((*mindis)[u]+w < (*mindis)[v])
            {
                pq.push(Distance(v, (*mindis)[u]+w));
            }
        }
    }
    return mindis;
}

bool operator> (const Distance &a, const Distance &b)
{
    return a.dis > b.dis;
}

bool operator< (const Node &a, const Node &b)
{
    if(a.v < b.v)
    {
        return true;
    }
    return a.w < b.w;
}

int Graph::inf()
{
    return 1e9+721;
}