#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2e9
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <pair<int,int> > v[50001];
priority_queue <pair<int,int>,vector <pair<int,int> >,greater <pair <int,int> > >h;
int d[50001],n,m,x,y,c,i;
void dijkstra(int s)
{int i,nod,vecin,cost;
for(i=1;i<=n;i++)d[i]=inf;
d[s]=0;
h.push(make_pair(0,s));
while(!h.empty())
    {nod=h.top().second;
    cost=h.top().first;
    h.pop();
    if(d[nod]!=cost)continue;
    for(pair <int,int> i:v[nod])
        {vecin=i.second;
        cost=i.first;
        if(d[nod]+cost<d[vecin])
            {d[vecin]=d[nod]+cost;
            h.push(make_pair(d[vecin],vecin));
            }
        }

    }

}
int main()
{f>>n>>m;
for(i=1;i<=m;i++)
    {f>>x>>y>>c;
    v[x].push_back(make_pair(c,y));
    }
dijkstra(1);
for(i=2;i<=n;i++)
    if(d[i]==inf)g<<0<<" ";
    else g<<d[i]<<" ";
return 0; 
}