#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});
        lista[y].push_back({x,cost});

    }

}
int dp[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);
    while(!noduri.empty())
    {
       int nod=noduri.front();
       noduri.pop();
       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;
               noduri.push(vecin);
           }


       }

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

    }

}

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