#include <fstream>
#include <queue>

using namespace std;
ifstream cin ("bellmanford.in");
ofstream cout ("bellmanford.out");
int cap[350][350];
int cost[350][350];
long long dist[350];
queue<int>qu;
vector<int>adj[50];
void bellmanford(int st,int n)
{
    int curr,i,k;
    qu.push(st);
    while(qu.size())
    {
        curr=qu.front();
        qu.pop();
        for(i=0;i<adj[curr].size();i++)
        {
            k=adj[curr][i];
            if(dist[curr]+cost[curr][k]<dist[k] && cap[curr][k]!=0)
            {
                dist[k]=dist[curr]+cost[curr][k];
                qu.push(k);
            }
        }
    }
}
long long inf=1e14;
int main()
{
    int i,j,k,l,n,m,a,b,capedge,costedge,st,fs,cst,cp           ;
    cin>>n>>m;
    st=1;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>cst;
        cp=1;
        cap[a][b]=cp;
        adj[a].push_back(b);
        cost[a][b]=cst;
    }
    for(i=2;i<=n;i++)
    {
        dist[i]=inf;
    }
    bellmanford(st,n);
    for(i=2;i<=n;i++)
    {
        cout<<dist[i]<<" ";
    }
    return 0;

}