#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

#define pb push_back
#define mp make_pair

#define MAX 50001
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector < pair < int , int > > G[MAX] ;
vector < pair < int , int > >::iterator j;
int  USED[MAX] ;
int  D[MAX];
queue < int > Q;

int n,m,x,y,z,start;

void bellman_ford( int i )
{
    memset( D , INF , sizeof D);
    D[i] = 0;
    USED[i] = true;
    Q.push(i);
    int nod;

    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        USED[nod] = false;
        for ( j = G[nod].begin(); j != G[nod].end(); j++ )
        {
            if (  D[ (*j).first ] > D[nod] + (*j).second )
            {
                D[ (*j).first ] = D[nod] + (*j).second;
                if( !USED[ (*j).first ] )
                {
                    Q.push( (*j).first);
                    USED[ (*j).first ] = true;
                }
            }
        }
    }
}

int main()
{
    f >> n >> m;

    for ( ; m-- ;  )
    {
        f >> x >> y >> z;
        G[x].pb(mp (y,z) );
    }

    start = 1;

    bellman_ford(start);

    for (int i = 2; i <= n ; ++i )
        g << D[i] << " " ;


    return 0;
} /*
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define NMAX 50001
#define INF 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

ifstream in("bellman_ford.in");
ofstream out("bellman_ford.out");

vector< pair< int, int > > G[NMAX];
vector< pair< int, int > >::iterator Vecin;
queue< int > Q;
int N, M, i, x, y, c, D[NMAX], It, ItNod[NMAX], Nod , start;
bool USED[NMAX];

int main()
{
    in >> N >> M >> start;
    for( ; M--; )
    {
        in >> x >> y >> c;
        G[x].pb( mp( y, c ) );
    }

    memset( USED, false, sizeof(USED) ); //initial nu avem noduri in coada
    memset( D, INF, sizeof(D) ); //toate distantele sunt infinit
    D[1] = 0; //mai putin cea pana la sursa
    memset( ItNod, 0, sizeof(ItNod) ); //nu s-a trecut niciodata prin niciun nod
    Q.push( 1 ); //introducem nodul 1 in coada
    USED[1] = true;

    while( !Q.empty() )
    {
        Nod = Q.front();
        Q.pop();
        USED[Nod] = false; // scoatem nodul din coada

        for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++ ) // iteram prin vecinii nodului
            if( D[(*Vecin).nod] > D[Nod] + (*Vecin).cost ) // incercand sa minimizam distanta pana la acestia
            {
                D[(*Vecin).nod] = D[Nod] + (*Vecin).cost;

                if( !USED[(*Vecin).nod] ) // daca nodul nu se afla in coada
                {
                    Q.push( (*Vecin).nod ); // il introducem
                    USED[(*Vecin).nod] = true;
                    if( ++ItNod[(*Vecin).nod] > N ) // dca s-a trecut de mai mult de N ori prin el
                    {
                        out << "Ciclu negativ!\n"; // inseamna ca in graf exista un ciclu negativ
                        return 0;
                    }
                }
            }
    }

    for( i = 2; i <= N; i++ )
        out << D[i] << ' '; // distantele de la nodul 1( sursa ) pana la celelalte noduri

    return 0;
}
*/