#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
#include <queue>
#include <climits>
using namespace std;

int main()
{
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,k,l,distanta[50001],vizitat[50001],parinte[50001];
vector<pair <int, int> > v[50001];
queue<int> q;
f>>n>>m;
for(i=1;i<=m;i++)
    {
    f>>j>>k>>l;
    v[j].push_back(make_pair(k,l));
    }
for(i=1;i<=n;i++)
    {
    distanta[i]=INT_MAX;
    vizitat[i]=0;
    parinte[i]=-1;
    }
q.push(1);
vizitat[1]=1;
distanta[1]=0;
while(!q.empty())
    {
    k=q.front();
    q.pop();
    for(i=0;i<v[k].size();i++)
        {
        if(vizitat[v[k][i].first]==0)
            {
            q.push(v[k][i].first);
            vizitat[v[k][i].first]=1;
            if(k==1)
                {
                distanta[v[k][i].first]=v[k][i].second;
                parinte[k]=k;
                }
            else
                {
                if(distanta[k]+v[k][i].second<distanta[v[k][i].first])
                    {
                    distanta[v[k][i].first]=distanta[k]+v[k][i].second;
                    parinte[v[k][i].first]=k;
                    }
                }
            }
        }
    }

for(i=2;i<=n;i++)
    {
    g<<distanta[i]<<" ";
    }
return 0;
}