I want to convert a matrix of nodes and distances into a table with columns for node1, node2 and the distance between them

Use DataFrame.stack here for better perfomance like pd.concat with list comprehension:

df2 = df.stack().rename_axis(['Node1','Node2']).reset_index(name='Distance')
print (df2.head(15))
    Node1 Node2  Distance
0       4     4         0
1       4    38      1280
2       4    71      1762
3       4    90      1406
4       4    94      1589
5       4  8545      1017
6      38     4      1280
7      38    38         0
8      38    71       681
9      38    90       202
10     38    94       385
11     38  8545      1433
12     71     4      1762
13     71    38       681
14     71    71         0

Another idea is use numpy:

c = np.tile(df.columns, len(df))
i = np.repeat(df.index, len(df.columns))
v = np.ravel(df)

df2 = pd.DataFrame({'Node1':i, 'Node2':c, 'Distance':v})

Performance:

#6k rows
df = pd.concat([df] * 1000, ignore_index=True)
# print(df)

In [37]: %timeit df2 = pd.DataFrame({'Node1':np.repeat(df.index, len(df.columns)), 'Node2':np.tile(df.columns, len(df)), 'Distance':np.ravel(df)})
1.77 ms ± 42.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [38]: %timeit df.stack().rename_axis(['Node1','Node2']).reset_index(name='Distance')
4.39 ms ± 475 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [39]: %timeit pd.concat([pd.DataFrame([[i, j, df.at[i, j]]], columns=['Node1', 'Node2', 'Distance']) for i in df.index   for j in df.columns], ignore_index=True)
31.6 s ± 1.22 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

For most graph operations, you'll find huge advantages if you work with graph libraries. In this case, you can easily create a graph from the dataframe and add those distances as edge weights.

Then for the desired output you'd just need to retrieve the graph edge's weights in this case, which can be easily done using NetworkX with:

import networkx as nx

G = nx.from_pandas_adjacency(df)
weights = nx.get_edge_attributes(G, 'weight')
print(weights)
{(94, 4): 1589,
 (94, 38): 385,
 (4, 38): 1280,
 (4, 71): 1762,
 (4, 90): 1406,
 (38, 71): 681,
 (38, 90): 202,
 (71, 90): 503}

Or if you want the result as a dataframe:

(pd.DataFrame(weights.keys(), columns=['node1', 'node2'])
    .assign(Distance=weights.values()))

   node1  node2  Distance
0     94      4      1589
1     94     38       385
2      4     38      1280
3      4     71      1762
4      4     90      1406
5     38     71       681
6     38     90       202
7     71     90       503

What I would to, is use Pandas stack, e.g.

import numpy as np
import pandas as pd

A = np.abs(1 - np.corrcoef( np.random.random( size=(8,8) ))) * 100

A is just to have some random more or less similar data.

We now create a df with

df = pd.DataFrame(A, columns = [ "node_" + str(i) for i in range(A.shape[0])])

         node_0      node_1      node_2      node_3      node_4      node_5  \
0  1.110223e-14  177.640823   94.528739  102.894884   75.716800   16.959874   
1  1.776408e+02    0.000000  100.594166   69.032398  106.857164  180.845071   
2  9.452874e+01  100.594166    0.000000  143.128873  154.447302  114.711230   
3  1.028949e+02   69.032398  143.128873    0.000000   25.162778  129.170641   
4  7.571680e+01  106.857164  154.447302   25.162778    0.000000   74.135700   
5  1.695987e+01  180.845071  114.711230  129.170641   74.135700    0.000000   
6  1.424585e+02   74.925019   70.156519   70.914395  125.433304  171.546764   
7  8.862326e+01   67.220779  139.488270   61.680713   58.115007   98.620041   

and you can df.stack()

df_stacked = df.stack()

You can make it a dataframe with pd.DataFrame( df_stacked )