#include <iostream>
#include <fstream>
#include <queue>

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

const int N= 50000;
const int M=250000;
const int INF=1e9;

struct muchie
{
    int from;
    int to;
    int cost;
};

std::vector<muchie> edge= {{0, 0, 0}};
std::vector<int> v[N+1];
bool visited[N+1];
int n, m=0, start;

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;

int rez[N+1];

int main()
{
    int x, y, c;

    in>>n>>start;
    for(int i=1; i<=n; i++) rez[i]=INF;
    while(in>>x>>y>>c)
    {
        m++;
        edge.push_back({x, y, c});
        v[x].push_back(m);
    }

    q.push({0, 1});

    while(!q.empty())
    {
        int top=q.top().second;
        int curr=q.top().first;

        if(!visited[top])
        {
            visited[top]=1;
            rez[top]=curr;

            for(int side : v[top])
            {
                if(!visited[edge[side].to])
                {
                   if(rez[top]+edge[side].cost<rez[edge[side].to])
                   {
                       q.push({rez[top]+edge[side].cost, edge[side].to});
                   }
                }
            }
        }

        q.pop();
    }

    for(int i=2; i<=n; i++)
    {
        out<<(rez[i]==INF ? 0 : rez[i])<<" ";
    }
}