#include <fstream>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int Nmax = 50005;
int dist[Nmax];
vector < pair<int, int> > vecini[Nmax];
void solve( int sursa )
{
    priority_queue < pair<int, int>> pq;
    pq.push({0, sursa});
    dist[sursa] = 0;
    while ( !pq.empty() )
    {
        auto [cost, nod] = pq.top();
        pq.pop();

      //  if ( dist[nod] < -cost )
          //  continue;


        for ( int i = 0; i < vecini[nod].size(); ++i )
        {
            auto [vecin, c] = vecini[nod][i];
            if ( dist[nod] + c < dist[vecin] )
            {
                dist[vecin] = dist[nod] + c;
                pq.push({-dist[vecin], vecin});
            }
        }
    }
}
int main()
{
    int n, m, i;
    fin >> n >> m;
    for ( i = 1; i <= m; ++i )
    {
        int a, b, c;
        fin >> a >> b >> c;
        vecini[a].push_back({b, c});
    }
    int INF = 1e9;
    for ( i = 1; i <= n; ++i )
        dist[i] = INF;
    solve(1);
    for ( i = 2; i <= n; ++i )
    {
        if ( dist[i] == INF )
            fout << "0 ";
        else
            fout << dist[i] << " ";

    }


    return 0;
}