#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <pair<int,int>> lista[100005];
void citire(int &n,int &m,int &p )
{
    int x,y,cost;
    p=1;
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        in>>x>>y>>cost;
        lista[x].push_back({y,cost});

    }

}
int dp[100005];
bool inq[100005];
void bellman_ford()
{
    int n,m,p;
    citire(n,m,p);
    queue <int> noduri;
    for(int i=1; i<=n; i++)
        dp[i]=-1;
    dp[p]=0;
    noduri.push(p);
    inq[p]=1;
    while(!noduri.empty())
    {
        int nod=noduri.front();
        noduri.pop();
        inq[nod]=0;
        for(auto elem:lista[nod])
        {
            int cost;
            int vecin=elem.first;
            cost=dp[nod]+elem.second;
            if(dp[vecin]==-1 || dp[vecin]>cost)
            {
                dp[vecin]=cost;
                if(inq[vecin]==0)
                {
                    noduri.push(vecin);
                    inq[vecin]=1;
                }
            }


        }

    }
    for(int i=2; i<=n; i++)
    {
        if(dp[i]==-1) out<<0<<" ";
        else out<<dp[i]<<" ";

    }

}

int main()
{
    bellman_ford();
    return 0;
}