#include <fstream>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,d[50002],k,x,y,cost;
bool marker[50002];
vector <pair <int,int> > v[50002];
priority_queue <pair <int,int>,vector <pair <int,int> >,greater < pair <int,int> > > Q;
void solve(int sursa)
{
    for(auto i: v[sursa])
    {
        Q.push(i);
        d[i.second]=i.first;
    }
    marker[sursa]=true;
    while(!Q.empty())
    {
        while(!Q.empty() && marker[Q.top().second])
        {
            Q.pop();
        }
        if(!Q.empty())
        {
            k=Q.top().second;
            marker[k]=true;
            Q.pop();
            for(auto i: v[k])
            {
                if(d[i.second]>d[k]+i.first)
                {
                    d[i.second]=d[k]+i.first;
                    Q.push({d[i.second],i.second});
                }
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        v[x].push_back({cost,y});
    }
    for(int i=2;i<=n;i++)
    {
        d[i]=inf;
    }
    solve(1);
    for(int i=2;i<=n;i++)
    {
        if(d[i]==inf)g<<"0 ";
        else g<<d[i]<<" ";
    }
    return 0;
}