#include<cstdio>
#include<set>
#include<vector>
using namespace std;
set<pair<int,int> > v;
vector<pair<int,int> > vec[50001];
int n,m,x,y,c;
int dist[50001];
void dijkstra()
    {int i,minim,nod;
    for(i=2;i<=n;i++)
        dist[i]=1000000000;
    dist[1] = 0;
    v.insert(make_pair(0,1));
    while(v.size()!=0)
        {minim=(*v.begin()).first;
        nod=(*v.begin()).second;
        v.erase(*v.begin());
        for(i=0;i<vec[nod].size();i++)
            if(dist[vec[nod][i].first]>vec[nod][i].second+dist[nod])
                {dist[vec[nod][i].first]=vec[nod][i].second+dist[nod];
                v.insert(make_pair(dist[vec[nod][i].first],vec[nod][i].first));
                }
        }
    for(i=2;i<=n;i++)
        if(dist[i]==1000000000)
            printf("0 ");
        else
            printf("%d ",dist[i]);
    }
int main()
{freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {scanf("%d%d%d",&x,&y,&c);
    vec[x].push_back(make_pair(y,c));
    }
dijkstra();
return 0;
}