#include<cstdio>
#include<set>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int> p;
vector<int> v[50001],v1[50001];
int vc[50001],vec[50001],i,j,n,m,x,y,l,cost;
int main ()
{
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&cost);
    v[x].push_back(y);
    v1[x].push_back(cost);
    }
for(i=2;i<=n;i++)
    vec[i]=1000000000;
for(i=0;i<v[1].size();i++)
    {
    vec[v[1][i]]=v1[1][i];
    vc[v[1][i]]=1;
    p.push(v[1][i]);
    }
while(!p.empty())
    {
    int x=p.top();
    p.pop();
    for(i=0;i<v[x].size();i++)
            if(vec[v[x][i]]>vec[x]+v1[x][i])
                {
                vec[v[x][i]]=vec[x]+v1[x][i];
                vc[v[x][i]]=1;
                if(vc[v[x][i]]==0)
                    p.push(v[x][i]);
                }
    vc[x]=0;
    }
for(i=2;i<=n;i++)
    printf("%d ",vec[i]);
return 0;
}