#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX = 50000;

int n, m;
int X, Y , Z;
int dist[NMAX];

struct muchie{
    int x, y;
    int m;
};

vector <muchie> graf[NMAX+1];

void dijkstra()
{
    set < pair<int,int> > mySet;
    mySet.insert( make_pair(0, 1) );
    dist[1] = 0;
    while(!mySet.empty())
    {
        int nrNod = mySet.begin() -> second;
        mySet.erase(mySet.begin());

        for( auto vecin : graf[nrNod] )
        {
            if(dist[vecin.y] > dist[vecin.x]+vecin.m)
            {
                mySet.erase( make_pair(dist[vecin.y], vecin.y) );
                dist[vecin.y] = dist[vecin.x]+vecin.m;
                mySet.insert( make_pair(dist[vecin.x]+vecin.m, vecin.y) );
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> X >> Y >> Z;
        muchie auxMuchie;
        auxMuchie.x = X;
        auxMuchie.y = Y;
        auxMuchie.m = Z;
        graf[X].push_back(auxMuchie);
    }
    for(int i=1; i<=n; i++)
        dist[i] = INT_MAX;
    dijkstra();
    for(int i=2; i<=n; i++)
        if(dist[i] == INT_MAX)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
    return 0;
}