Just giving two possibilities. There may be others more efficient but that can be a good start.
Let us take your case. You have a graph with 8 points. Say we index each point by an integer alphabetically: A=0,B=1,C=2,...H=7. You can represent them in supperposition using a 3-qubit register and the Hadamard transform. Add another 3-qubit register. This give us all possible connexions between points:
$$ \frac{1}{8} (| AA \rangle + | AB \rangle + | AC \rangle + ... + | GH \rangle) $$
Of course, in that case, we consider we can have loops and we also have connexions that may not exist in our graph.
Then using another register, you can compute the edge value for a connexion (using for example a controlled-adder circuit to add the edge value depending on the connexion computational basis):
$$ \frac{1}{8} (| AA \rangle + | AB \rangle + | AC \rangle + ... + | GH \rangle) | 0\rangle \rightarrow
\frac{1}{8} (| AA \rangle | 0\rangle + | AB \rangle | 5\rangle + | AC \rangle | 7\rangle + ... + | GH \rangle | 6\rangle)
$$
Also, another way I can think of is to assign an integer index to the connexion/edges of the graph themselves , which lets you work on only one register for storing the index. You just need enough qubits to have all edges indices in superposition. And again, use another register to compute their values like above.
Now for the search, you would look at the edge value register when searching.
You can use Durr and Hoyer's adaptation of Grover search to find the minimum. Or in your case, directly implement an oracle that recognizes the value 1 in the edge/value register (imagine this would be your first check/try to find the minimum) and use a simple Grover search.
