Thanks to recent advances in sensor technologies, detailed travel cost information are becoming increasingly available. Such data provide a solid data foundation to capture traffic uncertainty, e.g., in the form of travel cost distributions. We study the problem of estimating travel cost distributions of paths in a road network using floating car data. We consider two different distributions structures, namely histograms and Gaussian Mixture Models. Given a path and a departure time, we aim at estimating the travel cost distribution of the path. To this end, we propose a dual-input long-short term memory (DI-LSTM) model. We introduce two new gates with the purpose of combining two input distributions in every iteration, where one distribution is an edge’ distribution, and the other is the distribution of the pre-path until the edge, which is obtained from the previous DI-LSTM unit. Empirical studies on a large trajectory dataset offer insight into the design properties of the DI-LSTM and demonstrate that DI-LSTM out-performs classic LSTM, especially for longer paths. Furthermore, we determine that Gaussian Mixture Models has the potential to be a better suited distribution structure than histograms.